Java Recursion - Output from several recursive calls

Question

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

Miljen Mikic · Accepted Answer · 2016-06-02 08:22:21Z

1

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.

edited Jun 2, 2016 at 8:22

answered Jun 2, 2016 at 7:43

Miljen Mikic

15.3k8 gold badges64 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user2668836 Over a year ago

Makes perfect sense. Thank you so much.

Collectives™ on Stack Overflow

Java Recursion - Output from several recursive calls

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related