Problem
Given distinct candidates and a target, find all unique combinations where candidates sum to target. Each candidate may be used unlimited times.
Example
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]Solution
Backtracking. Try each candidate; recurse with reduced target. Prevent duplicates by tracking start index.
def combination_sum(candidates, target):
result = []
def backtrack(start, path, remain):
if remain == 0:
result.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remain: continue
path.append(candidates[i])
backtrack(i, path, remain - candidates[i])
path.pop()
backtrack(0, [], target)
return resultfunction combinationSum(candidates, target) {
const result = [];
function backtrack(start, path, remain) {
if (remain === 0) { result.push([...path]); return; }
for (let i = start; i < candidates.length; i++) {
if (candidates[i] > remain) continue;
path.push(candidates[i]);
backtrack(i, path, remain - candidates[i]);
path.pop();
}
}
backtrack(0, [], target);
return result;
}void backtrack(vector<int>& cand, int start, vector<int>& path, int remain, vector<vector<int>>& result) {
if (remain == 0) { result.push_back(path); return; }
for (int i = start; i < cand.size(); i++) {
if (cand[i] > remain) continue;
path.push_back(cand[i]);
backtrack(cand, i, path, remain - cand[i], result);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> path;
backtrack(candidates, 0, path, target, result);
return result;
}public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, 0, new ArrayList<>(), target, result);
return result;
}
private void backtrack(int[] cand, int start, List<Integer> path, int remain, List<List<Integer>> result) {
if (remain == 0) { result.add(new ArrayList<>(path)); return; }
for (int i = start; i < cand.length; i++) {
if (cand[i] > remain) continue;
path.add(cand[i]);
backtrack(cand, i, path, remain - cand[i], result);
path.remove(path.size() - 1);
}
}Complexity
- Time: O(N^(T/M))
- Space: O(T/M) recursion
Explanation
Passing i (not i+1) allows reusing the same candidate. Start index prevents duplicate combinations like [2,3] and [3,2].
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?