给定一个int数组和一个数n,计算使用整数求和的方法数

Question

我在面试准备中看到了这个问题.

给定一个int数组和一个数n,计算使用整数求和的方法数

以下代码是我的解决方案.我试图通过递归来解决这个问题.子问题是针对数组中的每个int,我们可以选择与否.

public static int count(List<Integer> list, int n) {
    System.out.print(list.size() + ", " + n);
    System.out.println();
    if (n < 0 || list.size() == 0)
      return 0;
    if (list.get(0) == n)
      return 1;
    int e = list.remove(0);
    return count(list, n) + count(list, n - e);
  }

我尝试使用[10,1,2,7,6,1,5]进行整数,并将n设置为8.结果应为4.但是,我得到0.我试图打印每层上的内容堆栈的调试,如代码中所示.以下是我所拥有的:

7, 8
6, 8
5, 8
4, 8
3, 8
2, 8
1, 8
0, 8
0, 3
0, 7
0, 2
0, 1
0, 6
0, 7
0, -2

这个结果让我很困惑.我认为它从开始到(0,3)看起来正确.从(0,7)开始,我看起来不对.我期待(1,7)那里.因为如果我理解正确的话,这就是对堆栈底层的第二个count(list,n - e)调用.下层的列表操作不应影响当前层上的列表.所以我的问题是:

1. 为什么它(0,7)而不是(1,7)基于我当前的代码？
2. 我应该对当前代码做什么调整才能得到正确的结果？

谢谢!

Answer 1

您的算法不起作用的原因是因为您在递归调用之前使用了一个正在修改的列表.

由于列表是通过引用传递的,最终发生的是你递归调用,remove直到列表中没有任何内容,然后你的所有递归调用将返回0

你可以做的是在每个递归步骤创建列表的两个副本.但是,这样效率太低了.

更好的方法是使用一个索引i来标记在调用期间正在查看的列表中的元素:

public static int count(List<Integer> list, int n, int i) {
    //System.out.print(list.size() + ", " + n);
    //System.out.println();
    if (n < 0 || i <= 0)
      return 0;

    int e = list.get(i);  // e is the i-th element in the list
    if (e == n)
      return 1 + count(list, n, i-1);   // Return 1 + check for more possibilities without picking e

    return count(list, n, i-1) + count(list, n - e, i-1);   // Result if e is not picked + result if e is picked
}

然后yourList.size() - 1,您将传递i初始函数调用.

还有一点是,当你return 1,你仍然需要添加多少可能性,以便你的元素e不被选中作为总和的一部分.否则,如果 - 例如 - 列表中的最后一个元素是n,则递归将在第一步结束,仅返回1而不检查更多可能的数字组合.

最后,您可能希望使用动态方法重写算法,因为这样可以为您提供更好的运行时间.