SHARE
TWEET

17. SubSetSumHarer

Teodor92 Jan 6th, 2013 388 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2.  
  3. class SubSetSumHarder
  4. {
  5.     static void Main()
  6.     {
  7.         Console.WriteLine("Enter the wanted sum of the subsets:");
  8.         long wantedSum = long.Parse(Console.ReadLine());
  9.        
  10.         Console.WriteLine("Enter the length of the subset");
  11.         int lenSub = int.Parse(Console.ReadLine());
  12.  
  13.         Console.WriteLine("Enter the number of elements:");
  14.         long numberOfElements = long.Parse(Console.ReadLine());
  15.  
  16.         long[] elements = new long[numberOfElements];
  17.         int counter = 0;
  18.         string subset = "";
  19.         for (int i = 0; i < elements.Length; i++)
  20.         {
  21.             Console.WriteLine("Enter element № {0}", i + 1);
  22.             elements[i] = long.Parse(Console.ReadLine());
  23.         }
  24.         int maxSubsets = (int)Math.Pow(2, numberOfElements);
  25.         for (int i = 1; i < maxSubsets; i++)
  26.         {
  27.             subset = "";
  28.             long checkingSum = 0;
  29.             int lenCounter = 0;
  30.             for (int j = 0; j <= numberOfElements; j++)
  31.             {
  32.                 int mask = 1 << j;
  33.                 int nAndMask = i & mask;
  34.                 int bit = nAndMask >> j;
  35.                 if (bit == 1)
  36.                 {
  37.                     checkingSum = checkingSum + elements[j];
  38.                     subset = subset + " " + elements[j];
  39.                     lenCounter++;
  40.                 }
  41.             }
  42.             if (checkingSum == wantedSum && lenCounter == lenSub)
  43.             {
  44.                 Console.WriteLine("Number of subest that have the sum of {0}", wantedSum);
  45.                 counter++;
  46.                 Console.WriteLine("This subset has a sum of {0} : {1} ", wantedSum, subset);
  47.             }
  48.         }
  49.         Console.WriteLine(counter);
  50.     }
  51. }
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