Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using System;
- using System.Linq;
- using System.Collections.Generic;
- public class ZeroSubSet
- {
- public static void Main()
- {
- // reading input the lazy way
- // works only if you input the numbers on one line with single space between them
- int[] numbers = Console.ReadLine().Split().Select(int.Parse).ToArray();
- // calculate possible combinations (including empty subset)
- int combinations = (int)Math.Pow(2, numbers.Length);
- // iterate through subsets and find those that have sum of 0
- // start at 0 to include the empty subset if you need it
- for(int i = 1; i < combinations; i++)
- {
- // create a list to store current combination
- List<int> currentSubSet = new List<int>();
- int currentSubsetSum = 0;
- // check where bits have value of 1 and add those numbers to the curent subset
- int currentCombination = i;
- int bitPosition = 0;
- // 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
- // this should be adjusted for bigger collections or just replace 5 with 32 (it won't slow your program down)
- // this number also equals the number of entered numbers so we can replace 5 with numbers.Length
- // note though that this could cause problems with arrays with more than 32 elements (use long then)
- while(bitPosition < 5)
- {
- if((currentCombination & 1) == 1)
- {
- // add number at current index to the current subset and to the subset sum
- currentSubSet.Add(numbers[bitPosition]);
- currentSubsetSum += numbers[bitPosition];
- bitPosition++;
- currentCombination >>= 1;
- }
- }
- // check if current sum is 0
- if (currentSubsetSum == 0)
- {
- // print current sub set
- Console.WriteLine(String.Join(" + ", currentSubSet));
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement