CODEWITHSUNDEEP
javaalgorithmrecursion
user2668836
user2668836

Reputation: 25

Java Recursion - Output from several recursive calls

My code here will generate all combinations (repetition included) of the values in candidates such that the values will sum up to target. This is my solution to https://leetcode.com/problems/combination-sum/.

I am a little confused about why I need to include the following line of code:

currentSet = new ArrayList<>(currentSet);

This will essentially make it so that currentSet is a private variable for all recursive calls. Otherwise, currentSet will be a shared variable that the recursive calls will concurrently modify resulting in issues. For example when the statement above is omitted from the code, combinationSum({1, 2}, 4) has the following output: 

[[1, 1, 2], [1, 1, 1, 1], [1, 2]]

The array [1,2] obviously does not sum up to 4. Can anybody provide a solid explanation why this is happening?

Also, are there any optimizations I could do so that my code can avoid putting in duplicate but reordered arrays, as my current method in brute-force sorting and checking if contained in the HashSet leads to very bad complexity. 

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> returnSet = new HashSet<>();
        returnSet = combSum(candidates, target, 0, returnSet, new ArrayList<Integer>());
        return new ArrayList<>(returnSet);
    }

private Set<List<Integer>> combSum(int[] candidates, int target, int i, Set<List<Integer>> returnSet,
    List<Integer> currentSet) {
    currentSet = new ArrayList<>(currentSet);
    if(i == target) {
        Collections.sort(currentSet);
        if(!returnSet.contains(currentSet)) {
            returnSet.add(new ArrayList<Integer>(currentSet));
        }
    } else if(i <= target){
        System.out.println("Current set: " + returnSet.toString());
        System.out.println("Current sum: " + i + " current target: " + target);
        for(int a: candidates) {
            if(i + a <= target) {
                System.out.println("\tAdding: " + a + " so that the new sum will be: " + (i + a));
                currentSet.add(a);
                returnSet = combSum(candidates, target, i + a, returnSet, currentSet);
                currentSet.remove(currentSet.size() - 1);
            }
        }
    }

    return returnSet;
}

Upvotes: 0

Views: 85

Answers (1)

Miljen Mikic
Miljen Mikic

Reputation: 15241

The line

currentSet = new ArrayList<>(currentSet);

is Java-way to call a copy constructor, i.e. you are creating new ArrayList which initially has all elements from the old list. However, the original list and new list are independent, so any change in the new list would not be reflected to the original list. This is important in your algorithm because of these lines:

            currentSet.add(a);
            returnSet = combSum(candidates, target, i + a, returnSet, currentSet);
            currentSet.remove(currentSet.size() - 1);

Here you are adding an element at the end of the list, finding all possible recursive combinations with that element, and removing it later to try with another one. If you didn't make a copy of the list in the recursive call, currentSet variable would be modified and the line

currentSet.remove(currentSet.size() - 1);

would not remove the element you added before the recursive call, but some other element that was added within a recursion - don't forget that you are sorting elements within a recursion, so the original order will not be always preserved. That's what happened in your example when you omitted the copy constructor.

Possible optimization

What naturally comes to my mind is to sort the initial array of the candidates at the beginning, in the combinationSum method. Iterating through the sorted array will avoid duplicates and you wouldn't need to check for duplicate results.

Upvotes: 1

Related Questions