CODEWITHSUNDEEP
javarecursionbacktracking
Junxu Chen
Junxu Chen

Reputation: 71

Recursion confusion of list

Here's the problem

numberSet = [2,3,5], target number = 8
output -> [[2,2,2,2],[2,3,3],[3,5]]

And I think it can be solved by backtracking:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new LinkedList<>();
    permutation(candidates, target, new LinkedList(), result);
    return result;
}

public void permutation(int[] candidates, int target, List<Integer> subresult, List<List<Integer>> result){
    if(target == 0){
        result.add(subresult);
        return;
    }
    for(int x: candidates){
        if(target - x >= 0){
            subresult.add(x);
            permutation(candidates, target - x, subresult, result);
            subresult.remove(subresult.size() - 1);
        }
    }
        return;
}

Everything makes sense to me, however, my output is:

[[],[],[],[]]

They are all empty list... I want to figure out why so I print out each step when the condition

if(target == 0){
        result.add(subresult);
        System.out.println(result);
        return;
    }

is satisfied. And I think my code do find the solution(even I haven't figured out how to remove those duplicates)

[[2, 2, 3]]
[[2, 3, 2], [2, 3, 2]]
[[3, 2, 2], [3, 2, 2], [3, 2, 2]]
[[7], [7], [7], [7]]

Why would this happen??? Why is the result list still empty? Thanks sooo much!

Upvotes: 0

Views: 45

Answers (1)

Vishal
Vishal

Reputation: 404

Your approach is correct, but since you're removing the last value of subresult- subresult.remove(subresult.size() - 1); in every recursive method call, and since result only adds a reference to the subresult, so every add/remove operation on the subresult would be changed in the result also.

In short-

If subresult is [1,2,3] and you add this in result, then result = [1,2,3]

But now if you remove 3 from subresult, then result also becomes [1,2]

So in order to avoid that,

result.add(new LinkedList<Integer>(subresult));

This creates a new List object with the values of the passed in list.

Upvotes: 1

Related Questions