Java中的递归方法，返回一个整数数组列表（只有一个），求和为一个数字，如果没有，则为空

Question

我试图使用递归编写一个方法subsetWithSum（ArrayList numbers，int sum），该方法获取整数的ArrayList和整数的和，并返回一个ArrayList，其中包含给定数字（提供的ArrayList）中的数字，这些数字的和等于和。不必返回多个组合，如果没有这样的子集，则应返回null。但我的代码只为每个返回null``

这是我的方法代码：

public static ArrayList<Integer> subsetWithSum(ArrayList<Integer> numbers, int sum){
    ArrayList<Integer> sumList=new ArrayList<Integer>();
    int sumForNumbers=0;
    for (int i=0; i<=numbers.size()-1; i++)
        sumForNumbers+=numbers.get(i);
    if (sumForNumbers==sum)
        return numbers;
    else if(sumForNumbers>sum || numbers.size()==0)
        return null;
    else {
        for (int i=0; i<numbers.size();i++){
        int n=numbers.get(i);
        for (int currentIndex=i+1; currentIndex<numbers.size(); currentIndex++)
            sumList.add(numbers.get(currentIndex));
        for (int currentIndex=0; currentIndex<=numbers.size()-1;currentIndex++){
            if ((sumForNumbers+numbers.get(currentIndex))<=sum){
                sumList.add(numbers.get(currentIndex));
                sumForNumbers+=numbers.get(currentIndex);
            }
        }
    }
        return subsetWithSum(sumList, sum);
    }
}

下面是我对该方法的主要调用：

    public static void main(String[] args) {
    ArrayList<Integer> test = new ArrayList<Integer>();
    test.add(3); test.add(11); test.add(1); test.add(5);
    System.out.println("Available numbers: " +test);
    for(int sum=16; sum<=19; sum++){
        ArrayList<Integer> answer = subsetWithSum(test, sum);
        System.out.println(sum+" can be made with: "+answer);

以下是我当前的输出：

Available numbers: [3, 11, 1, 5]`
16 can be made with: null
17 can be made with: null
18 can be made with: null
19 can be made with: null

我的预期输出是：

Available numbers: [3, 11, 1, 5]
16 can be made with: [11, 5]
17 can be made with: [11, 1, 5]
18 can be made with: null
19 can be made with: [3, 11, 5]

我发现递归很难理解，任何帮助都会很好

Answer 1

你应该注意的第一件事是这个问题是NP完全问题。这意味着它的运行时间不是多项式。最著名的算法是指数算法。如果你找到一个多项式算法来解决它，并且你能证明它是正确的，那么你将赢得100万美元。）

参考号：https://en.m.wikipedia.org/wiki/Subset_sum_problem

现在，在这种情况下，您可以应用回溯模式：

https://en.m.wikipedia.org/wiki/Backtracking

只需将伪代码翻译成Java并实现函数。如果你学习这种模式并练习将其用于不同的问题，你会学到很多关于递归的知识。

Answer 2

首先，如果您使用的是Java 8，请对列表求和

其次，递归总是采用类似的形式：

func(context)
    if context in simple form
        return simple result
    else
        break context down into smaller pieces
        call func on smaller pieces

对你来说，看起来像是

func(total, list)
    if sum(list) == total
        return list
    else if list is not empty
        get all solutions from func(total - first item, list without first item)
        and func(total, list without first item)

这里需要考虑一些棘手的事情：

• 如何处理返回列表以及列表是否为有效结果
• 如何删除项，然后在递归调用后将其添加回

这是一个带有测试用例的示例解决方案。

public class ListSum {

    public static void main(String[] args) {
        subsetsThatSumTo(18, Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)).forEach(System.out::println);
    }

    public static List<List<Integer>> subsetsThatSumTo(int total, List<Integer> list) {
        List<List<Integer>> result = new ArrayList<>();
        if (list.stream().mapToInt(n -> n).sum() == total) {
            result.add(new ArrayList<>(list));
        } else if (!list.isEmpty()) {
            subsetsThatSumTo(total - list.get(0), list.subList(1, list.size())).forEach(result::add);
            result.forEach(l -> l.add(0, list.get(0)));
            subsetsThatSumTo(total, list.subList(1, list.size())).forEach(result::add);
        }
        return result;
    }
}

如果您只想返回第一个结果：

public class ListSum {

    public static void main(String[] args) {
        System.out.println(subsetThatSumTo(18, Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)));
    }

    public static List<Integer> subsetThatSumTo(int total, List<Integer> list) {
        if (list.stream().mapToInt(n -> n).sum() == total)
            return new ArrayList<>(list);
        if (list.isEmpty())
            return null;
        List<Integer> result = subsetThatSumTo(total - list.get(0), list.subList(1, list.size()));
        if (result != null) {
            result.add(0, list.get(0));
            return result;
        } else {
            return subsetThatSumTo(total, list.subList(1, list.size()));
        }
    }
}