find elements summing to s in an array

问题:

given an array of elements (all elements are unique ) , given a sum s find all the subsets having sum s. for ex array {5,9,1,3,4,2,6,7,11,10} sum is 10 possible subsets are {10}, {6,4}, {7,3}, {5,3,2}, {6,3,1} etc. there can be many more. also find the total number of these subsets. please help me to solve this problem..

回答1:

It is a famous backtracking problem which can be solved by recursion. Basically its a brute force approach in which every possible combination is tried but 3 boundary conditions given at least prune the search.
Here is algorithm:
s variable for the sum of elements selected till now.
r variable for the overall sum of the remaining array.
M is the sum required.
k is index starting with 0
w is array of given integers

Sum(k,s,r)
{
    x[k]:=1;  //select the current element
    if(s<=M & r>=M-s & w[k]<=M-s)
    then
    {
        if(s+w[k]==M)
        then output all i [1..k] that x[i]=1
        else
        sum(k+1,s+w[k],r-w[k])
    }
    x[k]:=0  //don't select the current element
    if(s<=M) & (r>=M-s) & (w[k]<=M-s)
    then
    {
        if (M==s)
        then output all i [1..k] that x[i]=1
        else
        sum(k+1,s,r-w[k])
    }
}

I am using an array "x" to mark the candidate numbers selected for solution. At each step 3 boundary conditions are checked:

1. Sum of selected elements in "x" from "w" shouldn't exceed M. s<M.    
2. Remaining numbers in array should be able to complete M. r>=M-s.
3. Single remaining value in w shouldn't overflow M. w[k]<=M-s.  

If any of the condition is failed, that branch is terminated.

回答2:

Here's some python code doing what you want. It makes extensive use of itertools so to understand it you might want to have a look at the itertools docs.

>>> import itertools
>>> vals = (5,9,1,3,4,2,6,7,11,10)
>>> combos = itertools.chain(*((x for x in itertools.combinations(vals, i) if sum(x) == 10) for i in xrange(len(vals)+1)))
>>> for c in combos: print c
...
(10,)
(9, 1)
(3, 7)
(4, 6)
(5, 1, 4)
(5, 3, 2)
(1, 3, 6)
(1, 2, 7)
(1, 3, 4, 2)

What it does is basically this:

• For all possible subset sizes - for i in xrange(len(vals)+1), do:
• Iterate over all subsets with this size - for x in itertools.combinations(vals, i)
• Test if the sum of the subset's values is 10 - if sum(x) == 10
• In this case yield the subset

For each subset size another generator is yielded, so I'm using itertools.chain to chain them together so there's a single generator yielding all solutions.

Since you have only a generator and not a list, you need to count the elements while iterating over it - or you could use list(combos) to put all values from the generator into a list (this consumes the generator, so don't try iterating over it before/after that).

回答3:

Since you don't say if it's homework or not, I give only some hints:

• let nums be the array of numbers that you can use (in your example nums = {5,9,1,3,4,2,6,7,11,10})

• let targetSum be the sum value you're given (in your example targetSum = 10)

• sort nums: you don't want to search for solutions using elements of nums that are bigger of your targetSum

• let S_s be a set of integers taken from nums whose sum is equal to s

• let R_s be the set of all S_s

• you want to find R_s (in your example R_10)

• now, assume that you have a function find(i, s) which returns R_s using the the sub-array of nums starting from position i

  • if nums[i] > s you can stop (remember that you have previously sorted nums)

  • if nums[i] == s you have found R_s = { { nums[i] } }, so return it

  • for every j in [1 .. nums.length - 1] you want to compute R_s' = find(i + j, targetSum - nums[i]), then add nums[i] to every set in R_s', and add them to your result R_s

• solve your problem by implementing find, and calling find(0, 10)

I hope this helps