首页 文章

Java中的一个递归方法，它返回一个整数的arrayList（只是其中一个），它总结为一个数字，如果没有则返回null

提问于
浏览 次
0

我试图使用递归来编写方法subsetWithSum（ArrayList numbers，int sum），它接受一个整数和整数和的数组，并返回一个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);
    }
}

这是我对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]

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

java recursion arraylist

2 回答

  • 0

    首先，如果您使用的是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()));
        }
    }
}
    回复于
  • 0

    你应该注意的第一件事是这个问题是NP-Complete . 这意味着它的运行时间不是多项式的 . 最着名的算法是指数的 . 如果您找到一个多项式算法来解决它，并且您可以证明它是正确的，那么您赢得1M $;）

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

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

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

    只需将伪代码转换为Java并实现这些功能即可 . 如果你研究这种模式并练习将它用于不同的问题，你将学到很多关于递归的知识 .

    回复于

相关问题