SHARE
TWEET

SubSetSumBin

Teodor92 Nov 28th, 2012 115 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. class SubSetSumBin
  4. {
  5.     static void Main()
  6.     {
  7.         long wantedSum = long.Parse(Console.ReadLine());
  8.         long numberOfElements = long.Parse(Console.ReadLine());
  9.         long[] elements = new long[numberOfElements];
  10.         int counter = 0;
  11.         for (int i = 0; i < elements.Length; i++)
  12.         {
  13.             elements[i] = long.Parse(Console.ReadLine());
  14.         }
  15.         int maxSubsets = (int)Math.Pow(2, numberOfElements) - 1;
  16.         for (int i = 1; i <= maxSubsets; i++)
  17.         {
  18.             long checkingSum = 0;
  19.             for (int j = 0; j <= numberOfElements; j++)
  20.             {
  21.                 int mask = 1 << j;
  22.                 int nAndMask = i & mask;
  23.                 int bit = nAndMask >> j;
  24.                 if (bit == 1)
  25.                 {
  26.                     checkingSum = checkingSum + elements[j];
  27.                 }
  28.             }
  29.             if (checkingSum == wantedSum)
  30.             {
  31.                 counter++;
  32.             }
  33.         }
  34.         Console.WriteLine(counter);
  35.     }
  36. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top