SHARE
TWEET

16. SubSetSum

Teodor92 Jan 6th, 2013 876 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /* * We are given an array of integers and a number S.
  2.  * Write a program to find if there exists a subset of
  3.  * the elements of the array that has a sum S. Example:
  4.         arr={2, 1, 2, 4, 3, 5, 2, 6}, S=14  yes (1+2+5+6)
  5.  */
  6.  
  7. using System;
  8.  
  9. class SubSetSum
  10. {
  11.     static void Main()
  12.     {
  13.         Console.WriteLine("Enter the wanted sum of the subsets:");
  14.         long wantedSum = long.Parse(Console.ReadLine());
  15.         Console.WriteLine("Enter the number of elements:");
  16.         long numberOfElements = long.Parse(Console.ReadLine());
  17.         long[] elements = new long[numberOfElements];
  18.         int counter = 0;
  19.         string subset = "";
  20.         for (int i = 0; i < elements.Length; i++)
  21.         {
  22.             Console.WriteLine("Enter element № {0}", i + 1);
  23.             elements[i] = long.Parse(Console.ReadLine());
  24.         }
  25.         int maxSubsets = (int)Math.Pow(2, numberOfElements) - 1;
  26.         for (int i = 1; i <= maxSubsets; i++)
  27.         {
  28.             subset = "";
  29.             long checkingSum = 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.                 }
  40.             }
  41.             if (checkingSum == wantedSum)
  42.             {
  43.                 Console.WriteLine("Number of subest that have the sum of {0}", wantedSum);
  44.                 counter++;
  45.                 Console.WriteLine("This subset has a sum of {0} : {1} ", wantedSum, subset);
  46.             }
  47.         }
  48.         Console.WriteLine(counter);
  49.     }
  50. }
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