Advertisement
darighteous1

Untitled

Aug 3rd, 2015
216
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. using System;
  2. using System.Linq;
  3. using System.Collections.Generic;
  4.  
  5. public class ZeroSubSet
  6. {
  7. public static void Main()
  8. {
  9. // reading input the lazy way
  10. // works only if you input the numbers on one line with single space between them
  11. int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
  12.  
  13. // calculate possible combinations (including empty subset)
  14. int combinations = (int)Math.Pow(2, numbers.Length);
  15.  
  16. // iterate through subsets and find those that have sum of 0
  17. // start at 0 to include the empty subset if you need it
  18. for(int i = 1; i < combinations; i++)
  19. {
  20. // create a list to store current combination
  21. List<int> currentSubSet = new List<int>();
  22. int currentSubsetSum = 0;
  23.  
  24. // check where bits have value of 1 and add those numbers to the curent subset
  25. int currentCombination = i;
  26. int bitPosition = 0;
  27.  
  28. // the current combination is a 32 bit integer but we know in this case it will be maximum 31 (which is 1111) so we don't have to iterate all 32 bits
  29. // this should be adjusted for bigger collections or just replace 5 with 32 (it won't slow your program down)
  30. // this number also equals the number of entered numbers so we can replace 5 with numbers.Length
  31. // note though that this could cause problems with arrays with more than 32 elements (use long then)
  32. while(bitPosition < 5)
  33. {
  34. if((currentCombination & 1) == 1)
  35. {
  36. // add number at current index to the current subset and to the subset sum
  37. currentSubSet.Add(numbers[bitPosition]);
  38. currentSubsetSum += numbers[bitPosition];
  39.  
  40. bitPosition++;
  41.  
  42. currentCombination >>= 1;
  43. }
  44. }
  45.  
  46. // check if current sum is 0
  47. if (currentSubsetSum == 0)
  48. {
  49. // print current sub set
  50. Console.WriteLine(String.Join(" + ", currentSubSet));
  51. }
  52. }
  53.  
  54. }
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement