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开发者_StackOverflow 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..

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.

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).

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)