Find N number subset in Array that sum to 0 [Subset Sum problem, that returns the subset]

I am trying to practice the interview question in the title

For those who directly want to know my question , jump to "Smaller version of my Question" .

For more context , read on.

=>For N = 2, We can simply use a Map.

=>For N= 3, there is a n^2 solution : Finding three elements in an array whose sum is closest to a given number [Check the accepted answer, it actually give you a solution for sum to 0 , rather than upto as in title of the link]

I guess using the above link, we can have 3 pointers for N=4 and get a n^3 solution.

Anyways, the point I am making that eventually all these solutions are not going to scale as N grows. So I am looking for a general purpose solution

I think this can be derived from a subset sum problem Subset sum problem . However the solution [dynamic programming version] to this problem returns a boolean. I am looking to get the actual subset.

The boolean solution i开发者_开发知识库tself isn't completely natural to derive [in the sense you cant 'derive' the answer easily unless you have read it.. I had to write down an example to understand it]. Anyways, I am looking for a way to modify it to give me a subset rather than just a boolean.

Smaller version of my Question:

Modify this to return the actual subset than just the boolean

Let S[i] = true if we can make sum i and false otherwise.

S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
    for s = MaxSum downto i
        if ( S[s - i] == true )
            S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.

---

Just make S[s] contain the list of numbers that make that sum when it is possible:

Let S[i] = the list of numbers that make up that sum and false (or null, something distinct from an empty list) otherwise.

S[0] = empty list // we can always make sum 0: just don't choose any number
S[i] = null for all i != 0
for each number i in your input
    for s = MaxSum downto i
        if ( S[s - i] != null )
            S[s] = S[s-i] with i added; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.