CODEWITHSUNDEEP
javadepth-first-search
Peter
Peter

Reputation: 165

DFS one condition in it really confuse me

For 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.

My code is:

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

For above code, it gives me the output 6 (not 2); But when I change the last 2 line from:

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

to:

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

Then, the result becomes just right, it's 2, not 6. I really can't tell any difference between above and below code. Is there anyone could help me and tell me why above is wrong. Many thanks.

Upvotes: 2

Views: 73

Answers (1)

LookIntoEast
LookIntoEast

Reputation: 8798

There's NO need to add "DFS(A, k, target, i + 1);" Just remove this line.

Upvotes: 1

Related Questions