How to avoid duplicating the ArrayList on every recursive call

Question

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) {
            result.add(new ArrayList<>(list));
            return;
        }

        recUtil(result, candidates, list, sum, target, ind+1);
        list.add(candidates[ind]);
        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

[[],[]]

Instead of

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

I know it must be something stupid, so I was afraid to ask here. I am new to java, can anyone please explain why just adding the list to the result does not work.

Answer 1

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.