寻找给定和的数字子集

Question

使用递归，编写一个程序，给定一个整数列表和一个给定的总和，将找到所有子集的数字，其总和为给定的总和。计算发现的子集数量。如果不存在子集，则应指示未找到解决方案。例如，给定列表6、13、3、3和总和为19，您的程序应该找到两个解决方案：

6 + 13 = 19
13 + 3 + 3 = 19

将输入列表中的整数数量限制在最多20个整数。仅接受正整数，并使用0标记列表的结尾。 以下是一个示例运行：

Enter positive integers terminated with 0: 6 13 3 3 0
Enter the desired sum: 19
Solution 1:6 +13 =19
Solution 2: 13 +3 +3 =19
Found 2 solutions

这是我的代码，但它只能找到一个子集，我想要找到所有的子集。有什么帮助吗？

 public static boolean SubSetSum(int start, int[] nums, int target) {
        if (start >= nums.length) {
            return (target == 0);
        }
        if (SubSetSum(start + 1, nums, target - nums[start])) {

            System.out.println( nums[start] );
            return true;
        }
        if (SubSetSum(start + 1, nums, target)) {

            return true;
        }
        return false;

    }




    public static void main(String[] args) {

        int[] mySet = {4,1,3,2};
        int sum = 5;
        System.out.println("The Goal is : " + sum);

       SubSetSum(0,mySet, sum) ;
    }
}

- hashem ghosheh

---

作为调试提示，不要直接在if条件中调用该方法，而是创建一个布尔变量，其结果是SubSetSum()的调用。 - Brydenr

好的，看看你的代码。如果在任何时候 target==0，那么你就达到了目标，但你没有相应的代码。你只有在 start 到达数组末尾时才检查 target==0。所以一眼看去，这是最明显的问题。另一个调试提示是在函数的第一行打印出函数参数，这样你就可以跟踪所有的调用。 - Jason C

@ItamarGreen SO的问题指南（你知道的，在评论中通常会抱怨的那些）是：准确的问题描述，付出的努力，可编译的示例，实际和期望的输出。在我看来，它似乎符合所有标准。 - Jason C

@ItamarGreen 不管是硬件还是软件，这个问题都没问题。请重新考虑。 - Nikolas Charalambidis

@NikolasCharalambidis，你说得很对。我误解了问题，但是重新阅读后，我发现我错了。 - ItamarG3

Answer 1

您主要的问题是：

• 一旦找到解决方案，就立即返回
• 只考虑从左到右的数字解决方案

您需要做的是考虑原始列表的所有可能子列表来解决问题，例如，对于列表[A, B, C, D]，解决方案可能是[A, C, D]。因此，一个好的起点是编写能够创建列表的所有子列表的代码。为此，您需要有一个列表集合，可以聚合所有可能性。以下是一个示例，它通过从原始列表的副本中删除元素来实现此目的，但有许多方法可以实现此目的：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class ResursionTest {
    public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums) {
        if (nums.size() == 0) {
            return;
        }

        // add the current list as a possibility
        allSubsets.add(new ArrayList<>(nums));

        // then add a possibility that has one less
        for (int i = 0; i < nums.size(); i++) {
            final List<Integer> subset = new ArrayList<>(nums);
            subset.remove(i);
            findSubsets(allSubsets, subset);
        }
    }


    public static void main(String[] args) {
        final Integer[] array = {4, 1, 3, 2};
        final HashSet<List<Integer>> allSubsets = new HashSet<>();

        findSubsets(allSubsets, Arrays.asList(array));
        System.out.println(allSubsets);
    }
}

如果您运行此代码，将会看到输出结果，我们正在查找原始输入列表[4, 1, 3, 2]的所有子列表。

输出检查：

[[3, 2], [1], [4, 3], [2], [3], [1, 2], [4, 3, 2], [1, 3], [4], [4, 1, 2], [4, 1, 3], [4, 1, 3, 2], [4, 1], [1, 3, 2], [4, 2]]

然后只需添加加起来等于所需数字的子列表，而不是添加所有可能性。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class ResursionTest {
    public static void findSubsets(Set<List<Integer>> allSubsets, List<Integer> nums, int sum) {
        if (nums.size() == 0) {
            return;
        }

        int currentSum = 0;
        for (Integer num : nums) {
            currentSum += num;
        }

        // does the current list add up to the needed sum?
        if (currentSum == sum) {
            allSubsets.add(new ArrayList<>(nums));
        }

        for (int i = 0; i < nums.size(); i++) {
            final List<Integer> subset = new ArrayList<>(nums);
            subset.remove(i);
            findSubsets(allSubsets, subset, sum);
        }
    }


    public static void main(String[] args) {
        int sum = 5;
        final Integer[] array = {4, 1, 3, 2};
        final HashSet<List<Integer>> allSubsets = new HashSet<>();

        findSubsets(allSubsets, Arrays.asList(array), sum);
        System.out.println(allSubsets);
    }
}

答案检查：

[[3, 2], [4, 1]]

有一些优化可以对这段代码进行，我会留给你自己去完成。

- mvd

---

谢谢您的回复！但是在您编写的代码中，如果输入超过13个整数到数组中，代码将无法正常工作。 - hashem ghosheh

你尝试使用13个整数运行这个程序了吗？需要多长时间？ - ksm

Answer 2

基本问题在于您返回了错误的信息：您需要找到所有的解决方案，但是您只返回了一个布尔值来表示是否成功。相反，您需要构建一个解决方案列表。

基本情况：

• 如果目标=0，则成功。打印解决方案并增加计数器。
• 否则，如果目标小于0，则失败。
• 否则，如果您没有剩余物品，则失败。

递归情况：

您在基本思路上做得很好：同时使用当前数字和不使用当前数字进行递归。但是，您还可以传递一个使用此分支中使用的数字列表--这样，当您到达底部时，就可以打印该列表。处理此步骤的其他方法，但我认为这对于您的应用程序最简单。如果您不允许更改SubSetSum的签名，则将其用作“包装器”，并从其中调用您的真实函数，从空列表开始。

这能帮助您吗？您还可以检查有关此问题的几十个先前的问题。

- Prune

Answer 3

我的动态规划解决方案：

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        int target = sc.nextInt();
        int dp[] = new int[target+1];
        dp[0] = 1;
        int currSum = 0;
        for(int i = 0;i<n;i++){
            currSum += arr[i];
            for(int j =  Math.min(currSum,target);j>= arr[i];j--){
                dp[j] += dp[j-arr[i]];
            }
        }
        System.out.println(dp[target]);
        }
    }

时间复杂度 O(N*target)，空间复杂度 O(N)

- HeadAndTail