java - 查找具有给定总和的数字子集

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

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

您仍然可以使用此代码进行一些优化，我将留给您。