java - DFS 中的一个条件真的让我很困惑

Question

问题:

Given n distinct positive integers, integer k and a number target. Find k numbers where sum is target. Return how many solutions there are?

The test case here, is A[] = {1,2,3,4}, k = 2, target = 5. There are 2 solutions: [1,4] and [2,3]. So return 2.

我的代码是:

public class Solution {     
    private int res = 0;
    public int kSum(int[] A, int k, int target) {
        Arrays.sort(A);
        DFS(A, k, target, 0 );
        return res;
    }

    private void DFS(int[] A, int k, int target,    int idx) {
        if (target < 0) return;
        if (k == 0) {
            if (target == 0) res += 1;
            return;
        }

        for (int i = idx; i < A.length; i++ ) {
            DFS(A, k - 1, target - A[i],  i + 1);   
            DFS(A, k,     target,         i + 1);         
        }
    }
}

对于上面的代码，它给了我输出 6(不是 2)；但是当我更改最后两行时:

DFS(A, k - 1, target - A[i],  i + 1);   
DFS(A, k,     target,         i + 1);

到:

private void DFS(int[] A, int k, int target,  int idx,  List<Integer> temp) {

..

temp.add(A[i]);
DFS(A, k - 1, target - A[i],  i + 1,      temp);
temp.remove(temp.size() - 1);

然后，结果就变得恰到好处，是 2，而不是 6。我真的看不出上面和下面的代码有什么区别。有没有人可以帮助我并告诉我为什么上面是错误的。非常感谢。

Answer 1

无需添加 "DFS(A, k, target, i + 1);"只需删除此行。