subset sum task

[checho]

hi i have the next task to solve.
* We are given 5 integer numbers. Write a program that checks if the sum of some subset of them is 0.
* Example: 3, -2, 1, 1, 8  1+1-2=0.
do u have any other ideas then writing all the 31 if statements?

[apegram]

You can do this with a pair of loops. Including whitespace, using statements, and console output, I've coded a full program to work with a fixed array of integers in 28 lines.

I'll give you the general description of the looping structure, sort of like pseudocode, and you should see if you can solve it from there.

For all of the integers in the array
   From current integer to the end of the array
       Calculate current sum
       Check value of sum
       Output?

Questions to ask are when do you reset the current sum, how are you building your output, etc.

[checho]

doing it with for loop wasnt successful for me.
at the beginning we can make a 2 nested loops for calculating the sum of each element with each element something like this
int[] numbers = new int[102];

for (int i = 0; i<5; i++)
           {                
                   for (int j = 0; j<5; j++)
                  {

                  } 

           }

[checho]

doing it with for loop wasnt successful for me.
at the beginning we can make a 2 nested loops for calculating the sum of each element with each element something like this
int[] numbers = new int[102];
int sum;

for (int i = 0; i<5; i++)
           {                
                   for (int j = 0; j<5; j++)
                  {
                       number[i+5] =  number[i] +number[j]
                  } 

           }

i didint compile the code just wrote it here.
So this is how iam gonna go through each element + each element.
What about
a+b +c,
a+b+d
a+b+e
and then b+c +d and so on.
i dont see it how will it be convinient to be solved?

[apegram]

My original answer was based on contiguous subsets, so it would find a, b, and c, but not a, c, and e. To expand it to include sets of non-adjacent numbers, my algorithm would need to be scrapped in favor of something that can test any combination. For a 5 item array, a 5-layer nested loop structure would do the job (I've quickly put together one such structure and tested it). Unfortunately, that doesn't allow for much scalability if the rules were changed. What if somebody wanted to find 0-sum incontiguous subsets within an array of 10 items? 15 items? Would you keep adding layers to the loop structure?

No, it seems that some form of recursion may be needed to develop a scalable algorithm that would handle arrays of any length. I do not have such an algorithm in mind.

For contiguous subsets, the two layers I proposed earlier are sufficient for arrays of any length. As for your implementation of it above, alter the inner loop to not start at 0, but at the current value of the outer loop.

for (int outer = 0; outer < numbers.Length; outer++)
        {
            // code here?

            for (int inner = outer; inner < numbers.Length; inner++)
            {
                  // code here?

[apegram]

As an update, it is possible to use recursion to arrive at a list of unique non-contiguous subsets within a given array. From there, it is a simple task to find zero-sum subsets and display them (or do whatever is required with them).

The actual recursive function I came up with is not overly complex, but the thought process that gets you there requires some effort. Also, getting unique results was challenging, even when dealing with an array with all unique values. I got around it, although I'm not sure I handled it in the most efficient manner.

However, the vibe I'm getting is that this problem is for an introductory course and more than likely recursion isn't an expected solution, as it probably hasn't been covered. Would that be a correct assumption?

[apegram]

I feel horrible replying to this thread again without anyone else chiming in, but oddly enough this problem [non-contiguous subsets, not the zero-sum part] has bugged me. As I said, I tackled it recursively before, but I didn't think it was all that efficient of an approach, even though it worked. There was a lot of waste and even a sort of monitoring HashSet because I was getting some duplicated subsets and needed to only add a subset of numbers once. It was ugly.

My final approach, and one that I'm almost 100% totally satisfied with, eliminates the recursion. I arrived at it by turning myself into the process I wanted to program and worked with an array of 5 integers and just sort of typed the process into notepad what I wanted to happen.

Given an array of 1-2-3-4-5, I wanted to go through each integer and arrive at all subsets. Start at the first number, add it as a subset. Move to the second number, add it as a subset, and then create new subsets including that number for all of the other existing subsets. Third number, add it, create new subsets with all of the other existing subsets including that number, move to the next number. Etc. So the output would sort of go like this:

1	// start with subset of 1
2	// add subset of 2
1	2	// add 2 to subset of 1, add as new subset
3	// add subset of 3
1	3	// add 3 to subset of 1, add as new subset
2	3	// add 3 to subset of 2, add as new subset
1	2	3 // add 3 to subset of 1 & 2, add as new subset
4	// add subset of 4
1	4	// add 4 to subset of 1, add as new subset
2	4	// etc.
1	2	4
3	4
1	3	4
2	3	4
1	2	3	4
5
1	5
2	5
1	2	5
3	5
1	3	5
2	3	5
1	2	3	5
4	5
1	4	5
2	4	5
1	2	4	5
3	4	5
1	3	4	5
2	3	4	5
1	2	3	4	5

I literally typed that into notepad (sans comments, those are showing my thought process) as I was mentally going through what I wanted the program to be able to do. As I was performing the algorithm, I was able to arrive at the precise manner of telling the computer how to do it.

And this is what I arrived at.

static List<T[]> CreateSubsets<T>(T[] originalArray)
{
    List<T[]> subsets = new List<T[]>();

    for (int i = 0; i < originalArray.Length; i++)
    {
        int subsetCount = subsets.Count;
        subsets.Add(new T[] { originalArray[i] });

        for (int j = 0; j < subsetCount; j++)
        {
            T[] newSubset = new T[subsets[j].Length + 1];
            subsets[j].CopyTo(newSubset, 0);
            newSubset[newSubset.Length - 1] = originalArray[i];
            subsets.Add(newSubset);
        }
    }

    return subsets;
}

Generic function, creates a List of arrays of all possible subsets of an original array. Looking at it now, I'm mad that it took me so long to get there, but whatever. From there, as I said in prior posts, it's a simple task to extract all int[] subsets that are zero-sum.

[Geekitygeek]

You might wanna check this article. The subset sum problem is used to demonstrate the NP-Complete complexity class.

Also, hats off to apegram for simultaneously presenting a well written method and demonstrating the best way to right one :)

[ddanbe]

@apegram : In case you did not know(which I doubt) you just set out all the combinations of 5 elements in groups of 1 to 5 without repetition!
Look here.
Was working on this same problem using the combinatorial approach(trying to write a combination method:-/ ) and with your list of numbers you showed I missed a combination! Thanks for pointing that out, will let you know if I can come up with something usefull:)

[checho]

Here is all i needed. 10x for all replies.
* We are given 5 integer numbers. Write a program that checks if the sum of some subset of them is 0.
* Example: 3, -2, 1, 1, 8  1+1-2=0.

static void Main(string[] args)
        {  
            int[] numbers = new int[5];
            int counter = 0;
            for (int i = 0; i < 5; i++)
            {
                numbers[i] = Convert.ToInt32(Console.ReadLine());
            }

            for (int i = 1; i < 32; i++)
            {
                int sum = 0;
                for (int j = 0; j < 5; j++)
                {
                    sum += ((i >> j) & 1) * numbers[j];
                }
                if (sum == 0)
                {
                    counter++;
                }
            }
            Console.WriteLine(counter + " Subset sums = 0"); 

          
        }