java - Java 中的递归方法，返回一个整数数组列表(仅其中一个)，其总和为一个数字，如果没有则为 null

Question

我正在尝试使用递归来编写一个方法subsetWithSum(ArrayListnumbers, int sum)，该方法接受整数的arrayList和整数和并返回一个ArrayList，其中包含给定数字中的数字(提供的ArrayList)总和为sum。不必返回多个组合，如果没有这样的子集，则应返回 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);
    }
}

这是我对 main 中的方法的调用:

    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

首先，如果您使用的是 Java 8，则求和 List<Integer> list就像list.stream().mapToInt(n -> n).sum()一样简单.

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

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