javarecursionmemoryarraylistcoin-change

# How to avoid duplicating the ArrayList on every recursive call

I have been trying to solve this leetcode question Combination Sum

Given an array of distinct integers candidates and a target integer, >return a list of all unique combinations of candidates where the >chosen numbers sum to target. You may return the combinations in any >order.

The same number may be chosen from candidates an unlimited number of >times. Two combinations are unique if the frequency of at least one of >the chosen numbers is different.

And I came up with this solution:

``````class Solution {
public void recUtil(List<List<Integer>> result, int[] candidates, List<Integer> list, int sum, int target, int ind) {
if(sum>target || ind>=candidates.length) return;
if(sum==target) {
return;
}

recUtil(result, candidates, list, sum, target, ind+1);
recUtil(result, candidates, list, sum+candidates[ind], target, ind);
list.remove(list.size()-1);
}

public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();

recUtil(result, candidates, new ArrayList<>(), 0, target, 0);

return result;
}
}
``````

This solution does not work if I replace the 5th line `result.add(new ArrayList<>(list));` with `result.add(list);`

For the input:

[2,3,6,7]

And target `7`, I get two empty ArrayLists in the result ArrayList

[[],[]]

• This solution does not work if I replace the 5th line `result.add(new ArrayList<>(list));` with `result.add(list);`
Correct. You seem already to understand that the latter adds the working list itself, not a copy of it, so you should also understand that in that case, the subsequent invocations of `list.add()` and `list.remove()` affect the same list that you added to the result, however many times you added it. That's not what you want. To be able to return multiple solutions, you need multiple lists, just as your original code provides.