Advertisement
sashomaga

Subset Sum

Jan 7th, 2013
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.38 KB | None | 0 0
  1. using System;
  2. using System.Text;
  3. //We are given an array of integers and a number S. Write a program to find if
  4. //there exists a subset of the elements of the array that has a sum S
  5. class Program
  6. {
  7.     static void Main()
  8.     {
  9.         int[] myArray = {2, 1, 2, 4, 3, 5, 2, 6};
  10.         int wantedSum = 14;
  11.  
  12.         int count = (int)Math.Pow(2, myArray.Length);
  13.  
  14.         StringBuilder builder = new StringBuilder();
  15.         int testSum = 0;
  16.         bool isExist = false;
  17.         for (int i = 1; i <= count; i++)
  18.         {
  19.             for (int j = 0; j < myArray.Length; j++)
  20.             {
  21.                 if ((i >> j & 1) == 1)
  22.                 {
  23.                     if(testSum == 0)
  24.                     {
  25.                         builder.Append(myArray[j]);
  26.                     }
  27.                     else
  28.                     {
  29.                         builder.Append("+").Append(myArray[j]);
  30.                     }
  31.                     testSum += myArray[j];
  32.                 }
  33.             }
  34.             if (testSum == wantedSum)
  35.             {
  36.                 Console.WriteLine("Yes({0})", builder);
  37.                 isExist = true;
  38.             }
  39.             else
  40.             {
  41.                 testSum = 0;
  42.                 builder.Clear();
  43.             }
  44.         }
  45.         if (isExist == false)
  46.         {
  47.             Console.WriteLine("Sum not exist");
  48.         }
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement