Problem Description

Given a set of candidate numbers (i.e., candidates) and a target number (target), your task is to find all unique combinations in candidates where the candidate numbers sum to target. The same number may be chosen an unlimited number of times from candidates.

Note:

• All numbers including the target will be positive integers.
• The solution set must not contain duplicate combinations.

Consider the following examples:

Example 1: Input: candidates = [2,3,6,7], target = 7, The solution set is: [ [7], [2,2,3] ]

Example 2: Input: candidates = [2,3,5], target = 8, The solution set is: [ [2,2,2,2], [2,3,3], [3,5] ]

Solution Description

To solve this problem, we need to adopt the backtracking algorithm. The backtracking algorithm is a technique for finding all (or some) solutions to some computational problems, particularly constraint satisfaction problems. It incrementally builds candidates for the solutions, but immediately stops further incrementization as soon as it detects the candidate cannot possibly be extended to a valid solution.

The algorithm sorts the candidates array in ascending order, then recursively uses a depth-first search (dfs) function to try all possible combinations of candidates that sum up to the target.

The dfs function will be used to implement the backtracking. The function checks if the current target is less than zero and returns if true. If the target is zero, it adds the current path to the possible answers ans. If the target is greater than zero, it loops through the candidates from the starting index s. It tries to subtract the current candidate from the target, adds the current candidate to the current path and recursively calls dfs. Finally, it removes the current candidate from the path - this is the backtracking part.

Python Solution:

1
2python
3class Solution:
4    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
5        def dfs(candidates, target, s, path, ans):
6            if target < 0: 
7                return
8            if target == 0: 
9                ans.append(path)
10                return
11            for i in range(s, len(candidates)):
12                dfs(candidates, target - candidates[i], i, path + [candidates[i]], ans)
13
14        ans = []
15        dfs(candidates, target, 0, [], ans)
16        return ans

Java Solution:

1
2java
3class Solution {
4    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
5        if(remain < 0) return;
6        else if(remain == 0) list.add(new ArrayList<>(tempList));
7        else{
8            for(int i = start; i < nums.length; i++){
9                tempList.add(nums[i]);
10                backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse elements
11                tempList.remove(tempList.size() - 1);
12            }
13        }
14    }
15
16    public List<List<Integer>> combinationSum(int[] candidates, int target) {
17        List<List<Integer>> list = new ArrayList<>();
18        Arrays.sort(candidates);
19        backtrack(list, new ArrayList<>(), candidates, target, 0);
20        return list;
21    }
22}

C++ Solution:

1
2c++
3class Solution {
4public:
5    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
6        sort(begin(candidates), end(candidates));
7        vector<vector<int>> res;
8        vector<int> combination;
9        combinationSum(candidates, target, res, combination, 0);
10        return res;
11    }
12private:
13    void combinationSum(vector<int> &candidates, int target,
14          vector<vector<int>> &res, vector<int> &combination, int begin) {
15        if (!target) {
16            res.push_back(combination);
17            return;
18        }
19        for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) {
20            combination.push_back(candidates[i]);
21            combinationSum(candidates, target - candidates[i], res, combination, i);
22            combination.pop_back();
23        }
24    }
25};

JavaScript Solution:

JavaScript also uses a similar method for implementing the backtracking algorithm. Here, we use the built-in JavaScript array methods push and pop to modify the current path.

1
2javascript
3var combinationSum = function(candidates, target) {
4    let res = [];
5    candidates.sort((a, b) => a - b);
6    let dfs = (target, start, current) => {
7        if(target === 0) {
8            res.push(current.slice());
9            return;
10        }
11        for(let i = start; i < candidates.length; i++) {
12            if(candidates[i] > target) return;
13            current.push(candidates[i]);
14            dfs(target-candidates[i], i, current);
15            current.pop();
16        }
17    };
18    dfs(target, 0, []);
19    return res;
20};

In this solution, we sort the candidates, and then use the dfs function to perform our depth-first search.

If the target matches zero, we’ve found a valid combination, and add it to our results array (res). We then continue to look for more combinations starting from the next index in the candidates array.

If the current candidate is greater than the target, we know that this candidate and those after it cannot be part of the solution (since the candidates are sorted), hence we return.

If the current candidate is less than or equal to the target, we add it to the current combination (current) and make a recursive call to dfs, passing the new target and the current combination. After the recursive call, we remove the current candidate from current before proceeding to the next candidate. This ensures that we do not include duplicate combinations in the result as well as explore all possible combinations.