在数组中查找总计为s的元素 [英] find elements summing to s in an array

问题描述

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

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

推荐答案

这是一个著名的回溯问题，可以通过递归来解决。基本上是一种蛮力方法，其中尝试了所有可能的组合，但至少给出了3个边界条件，以简化搜索。

这是算法：

s变量，表示所选元素的总和，直到现在。

r变量表示剩余数组的总和。

M是所需的总和。

k是从0
$ b $开始的索引bw是给定整数的数组

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

我正在使用数组 x标记为解决方案选择的候选编号。在每个步骤3中，检查边界条件：

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.

这篇关于在数组中查找总计为s的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！