获取具有目标总和的数组子集的算法无法正常工作

Question

问题是给定一个未排序的数组，给出可以产生目标总和的数组子集：

例如：

target =  15
data = {3,4,5,7,1,2,9};

预期结果（请注意，为简单起见，对结果进行了排序。不是必需的）：

[1, 2, 3, 4, 5]
[1, 2, 3, 9]
[1, 2, 5, 7]
[1, 3, 4, 7]
[1, 5, 9]
[2, 4, 9]
[3, 5, 7]

这是我解决这个问题的幼稚方法 - 简单而蛮力。

public static void naiveSubset(int[] arr, int target){
        int sum=0;
        List<Integer> result = new ArrayList<>();
        for (int i=0; i< arr.length;i++){
                sum =arr[i];
                result.add(arr[i]);
         for (int j=0;j<arr.length;i++){
             if (sum==target){
                 System.out.println(result);
                 result.clear();
                 break;
             }
             else if (i!=j && sum+arr[j] <= target){
                 sum+=arr[j];
                 result.add(arr[j]);
               }
           }
         }
        }

出于某些原因，我并不期待结果。我尝试浏览代码以找出任何问题。但我找不到任何。请算法专家为我指明正确的方向！！

我得到的结果（与上面相同的输入）

[3, 3, 3, 3, 3]
[9, 3, 3]

Answer 1

你的解决方案是错误的，因为它是一种贪婪的方法。它决定你是否应该添加一个数字，基于添加它不违反总和的事实。

但是，这种贪婪的方法不起作用，下面是一个简单的数组示例：[1,9,6,5] 和 sum=11.

请注意，对于您在外循环中选择的任何元素，接下来您将向当前集合添加 1。但这将使您无法获得 5+6 的总和。
一旦你选择了5，你就开始添加数字，从'1'开始，然后添加它。一旦添加 - 您将永远无法获得正确的解决方案。

另请注意：您的双循环方法最多可以生成 O(n^2) 个不同的子集，但子集的数量可能呈指数级增长 - 所以一定有问题。

如果你想得到所有可能的子集总和为给定的总和，你可以使用递归解决方案。

在每一步 "guess" 当前元素是否在集合中，并针对较小问题的两个选项递归 - 如果数据在集合中，或者不在集合中。

这是一个简单的 java 代码：

public static void getAllSubsets(int[] elements, int sum) {
    getAllSubsets(elements, 0, sum, new Stack<Integer>());
}
private static void getAllSubsets(int[] elements, int i, int sum, Stack<Integer> currentSol) { 
    //stop clauses:
    if (sum == 0 && i == elements.length) System.out.println(currentSol);
    //if elements must be positive, you can trim search here if sum became negative
    if (i == elements.length) return;
    //"guess" the current element in the list:
    currentSol.add(elements[i]);
    getAllSubsets(elements, i+1, sum-elements[i], currentSol);
    //"guess" the current element is not in the list:
    currentSol.pop();
    getAllSubsets(elements, i+1, sum, currentSol);
}

请注意，如果您要查找所有子集，则这些子集的数量可能呈指数级增长 - 因此预计会出现效率低下且呈指数级时间的解决方案。

如果您要查找是否存在这样的集合，或者只查找一个这样的集合，使用动态规划可以更有效地完成此操作。解释了如何做到这一点的逻辑。
注意问题还是NP-Hard，"efficient"解其实只是伪多项式

Answer 2

我认为您之前的方法的主要问题是简单地根据输入数组进行循环不会涵盖与目标值匹配的所有数字组合。例如，如果您的主循环在 ith 中，并且在您在次级循环中遍历 jth 元素之后，您未来基于通过第 i 个元素收集的内容的组合将永远不会包含 [=12] =] 一个了。直观上来说，这个算法会把所有可见的组合都通过数字相近，相距不远的组合收集起来。

我通过C++写了一个迭代的方法来处理这个子集和问题（抱歉，hand:P没有java的环境），思路和递归的方法基本一样，这意味着您将在循环的每次迭代中记录所有现有的数字组合。我有一个vector<vector> intermediate用来记录所有遇到的小于target的组合，vector<vector> final用来记录所有和等于target的组合。

内联记录详细解释：

/* sum the vector elements */
int sum_vec(vector<int> tmp){
    int sum = 0;
    for(int i = 0; i < tmp.size(); i++)
        sum += tmp[i];
    return sum;
}

static void naiveSubset(vector<int> arr, int target){
    /* sort the array from big to small, easier for us to
     * discard combinations bigger than target */
    sort(arr.begin(), arr.end(), greater<int>());

    int sum=0;
    vector<vector<int> > intermediate;
    vector<vector<int> > final;
    for (int i=0; i< arr.size();i++){
        int curr_intermediate_size = intermediate.size();
        for(int j = 0; j < curr_intermediate_size; j++){
            int tmpsum = sum_vec(intermediate[j]);
            /* For each selected array element, loop through all 
             * the combinations at hand which are smaller than target,
             * dup the combination, put it into either intermediate or 
             * final based on the sum */
            vector<int> new_comb(intermediate[j]);
            if(tmpsum + arr[i] <= target){
                new_comb.push_back(arr[i]);
                if(tmpsum + arr[i] == target)
                    final.push_back(new_comb);
                else
                    intermediate.push_back(new_comb);
            }
        }
        /* finally make the new selected element a separate entry
         * and based on its value, to insert it into either intermediate
         * or final */
        if(arr[i] <= target){
            vector<int> tmp;
            tmp.push_back(arr[i]);
            if(arr[i] == target)
                final.push_back(tmp);
            else
                intermediate.push_back(tmp);
        }
    }
    /* we could print the final here */
}

刚刚写的，如果有任何我没有考虑好的极端情况，请多多包涵。希望这有帮助:)

获取具有目标总和的数组子集的算法无法正常工作

algorithm to get subset of array with target sum is not giving working

java

arrays

algorithm

subset

subset-sum