Advertisement
sashomaga

Find subset

Jan 7th, 2013
37
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.72 KB | None | 0 0
  1. using System;
  2. //Write a program that reads three integer numbers N, K and S and an array of N elements from the console.
  3. //Find in the array a subset of K elements that have sum S or indicate about its absence
  4. class Program
  5. {
  6.     static void Main()
  7.     {
  8.         Console.Write("Enter the length of the array: ");
  9.         int arrayLength = int.Parse(Console.ReadLine());
  10.         Console.Write("Enter K: ");
  11.         int limit = int.Parse(Console.ReadLine());
  12.         Console.Write("Enter wanted sum: ");
  13.         int wantedSum = int.Parse(Console.ReadLine());        
  14.         int[] myArray = new int[arrayLength];
  15.         Console.WriteLine("Enter the array members:");
  16.         for (int i = 0; i < arrayLength; i++)
  17.         {
  18.             myArray[i] = int.Parse(Console.ReadLine());
  19.         }
  20.        
  21.  
  22.         int count = (int)Math.Pow(2, myArray.Length);
  23.  
  24.        
  25.         int testSum = 0;
  26.         int subsetMemberCount = 0;
  27.         bool isExist = false;
  28.         for (int i = 1; i <= count; i++)
  29.         {
  30.             for (int j = 0; j < myArray.Length; j++)
  31.             {
  32.                 if ((i >> j & 1) == 1)
  33.                 {
  34.                     testSum += myArray[j];
  35.                     subsetMemberCount++;
  36.                 }
  37.             }
  38.             if (testSum == wantedSum && limit == subsetMemberCount)
  39.             {
  40.                 isExist = true;
  41.                 break;
  42.             }
  43.             else
  44.             {
  45.                 testSum = 0;
  46.                 subsetMemberCount = 0;
  47.             }
  48.         }
  49.         if (isExist == false)
  50.         {
  51.             Console.WriteLine("Sum not exist");
  52.         }
  53.         else
  54.         {
  55.             Console.WriteLine("Sum exist");
  56.         }
  57.     }
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement