Combination Sum

Given an array of distinct integers candidates and a target integer target, 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.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Constraints:

  • 1 <= candidates.length <= 30
  • 1 <= candidates[i] <= 200
  • All elements of candidates are distinct.
  • 1 <= target <= 500

Intuition

Backtracking is a technique based on an algorithm to solve a problem. It uses recursive calling to find the solution by building a solution step by step increasing values with time. It removes the solutions that don’t give rise to the solution of the problem based on the constraints given to solve the problem.

Here, we could incrementally build the combination, and once we find the current combination is not valid, we will discard the current solution and backtrack to try another option.

To demonstrate the idea, we showcase how it works with a concrete example in the following graph:

For the given list of candidates [3, 4, 5] and a target sum 8, we start off from empty combination [] as indicated as the root node in the above graph.

  • Each node represents an action we take at a step, and within the node we also indicate the combination we build sofar.
  • From top to down, at each level we descend, we add one more element into the current combination.
  • The nodes marked in green are the ones that could sum up to the target value, i.e. they are the desired combination solutions.
  • The nodes marked in red are the ones that exceed the target value. Since all the candidates are positive value, there is no way we could bring the sum down to the target value, if we explore further.
  • At any instant, we can only be at one of the nodes. When we backtrack, we are moving from a node to its parent node.
An important detail on choosing the next number for the combination is that we select the candidates in order, where the total candidates are treated as a list. Once a candidate is added into the current combination, we will not look back to all the previous candidates in the next explorations.

To demonstrate the idea, let us zoom in a node (as we shown in the above graph) to see how we can choose the next numbers.

Choose combination in forward direction only
  • When we are at the node of [4], th previous candidate is [3], and the candidates followed are [4, 5].
  • We don’t add the previous numbers into the current node, since they would have been explored in the nodes in the left part of the subtree, i.e. the node of [3].
  • Even though we have already the element 4 in the current combination, we are giving the element another chance in the next exploration, since the combination can contain duplicate numbers.
  • As a result, we would branch out in two directions, by adding the element 4 and 5 respectively into the current combination.
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        List<List<Integer>> res = new ArrayList<>();
        if(candidates == null || candidates.length == 0){
            return res;
        }
        List<Integer> current_combination = new ArrayList<>();
        generateCombinations(candidates, current_combination, res, target, 0, 0);
        return res;
    }
    
    private void generateCombinations(int[] candidates, List<Integer> current_combination,
                                      List<List<Integer>> res,int target, 
                                      int current_sum, int start){
        
        if(target == current_sum){
            res.add(new ArrayList<>(current_combination));
            return;
        }
        else if(current_sum > target){
            return;
        }
        for(int i = start; i < candidates.length ; i++){
            int cur = candidates[i];
            current_combination.add(cur);
            generateCombinations(candidates, current_combination, res, target, (current_sum + cur), i);
            current_combination.remove(current_combination.size() - 1);
        }
    }
}

The worst-case time complexity is O(n!*n).

  • For any recursive function, the time complexity is O(BranchesDepth) * W.
    • Where W = amount of work at each node in the recursive call tree.

However, in this case, we have n(n-1)(n-2)(n-3)…1 branches at each level = n!, so the total recursive calls is O(n!). We do n-amount of work in each node by n element in the resulting ArrayList. So, the final complexcity is O(n!*n).

Categories: Backtracking

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s