Leetcode 39. Combination Sum
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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.