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 booleanLet 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.
精彩评论