algorithm - 在数组中查找总和为 s 的元素

Question

给定一个元素数组(所有元素都是唯一的)，给定一个总和s 找到所有具有总和 s 的子集。对于前数组 {5,9,1,3,4,2,6,7,11,10}总和是 10可能的子集是 {10}、{6,4}、{7,3}、{5,3,2}、{6,3,1} 等。可以有更多。还找到这些子集的总数。请帮我解决这个问题..

Answer 1

这是一个著名的回溯问题，可以通过递归来解决。基本上它是一种蛮力方法，其中尝试了所有可能的组合，但至少给出了 3 个边界条件来修剪搜索。
这是算法:
s 变量，表示到目前为止选择的元素的总和。
r 变量，表示剩余数组的总和。
M是所需的总和。
k 是从 0 开始的索引
w 是给定整数的数组

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])
    }
}

我正在使用数组“x”来标记为解决方案选择的候选数字。在每一步检查 3 个边界条件:

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.  

如果任何条件失败，则该分支终止。