LeetCode 39: Combination Sum (Backtracking + Reuse Candidates)
LeetCode 39BacktrackingDFSPruningToday we solve LeetCode 39 - Combination Sum.
Source: https://leetcode.com/problems/combination-sum/
English
Problem Summary
Given distinct positive integers candidates and a target integer target, return all unique combinations where chosen numbers sum to target. You may reuse the same candidate unlimited times.
Key Insight
Use DFS backtracking with a start index. From index i, we can pick candidates[i] and recurse with the same i (reuse allowed), or move forward to larger indices. This naturally avoids permutation duplicates like [2,3,2].
Brute Force and Limitations
Enumerating all integer multisets then checking sums is infeasible. Without pruning, recursion explores many dead branches. Sorting + early stop (value > remaining) removes most useless exploration.
Optimal Algorithm Steps
1) Sort candidates.
2) DFS state: (startIndex, remaining, path).
3) If remaining == 0, copy path to answer.
4) Iterate i from startIndex to end.
5) If candidates[i] > remaining, break (sorted pruning).
6) Add candidates[i], recurse with (i, remaining - candidates[i]), then pop.
Complexity Analysis
Worst-case time is exponential in solution depth/branching (backtracking enumeration). Practical performance is much better with pruning.
Space: O(target / minCandidate) recursion depth plus output storage.
Common Pitfalls
- Recursing with i + 1 after choosing a number (this incorrectly forbids reuse).
- Not copying path when adding to answer.
- Missing sort-based break, causing avoidable TLE on larger inputs.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public java.util.List<java.util.List<Integer>> combinationSum(int[] candidates, int target) {
java.util.Arrays.sort(candidates);
java.util.List<java.util.List<Integer>> ans = new java.util.ArrayList<>();
dfs(candidates, 0, target, new java.util.ArrayList<>(), ans);
return ans;
}
private void dfs(int[] c, int start, int remain,
java.util.List<Integer> path,
java.util.List<java.util.List<Integer>> ans) {
if (remain == 0) {
ans.add(new java.util.ArrayList<>(path));
return;
}
for (int i = start; i < c.length; i++) {
if (c[i] > remain) break;
path.add(c[i]);
dfs(c, i, remain - c[i], path, ans);
path.remove(path.size() - 1);
}
}
}import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}
path := []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if remain == 0 {
comb := make([]int, len(path))
copy(comb, path)
ans = append(ans, comb)
return
}
for i := start; i < len(candidates); i++ {
v := candidates[i]
if v > remain {
break
}
path = append(path, v)
dfs(i, remain-v)
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
dfs(candidates, 0, target, path, ans);
return ans;
}
void dfs(const vector<int>& c, int start, int remain,
vector<int>& path, vector<vector<int>>& ans) {
if (remain == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < (int)c.size(); ++i) {
if (c[i] > remain) break;
path.push_back(c[i]);
dfs(c, i, remain - c[i], path, ans);
path.pop_back();
}
}
};class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans: list[list[int]] = []
path: list[int] = []
def dfs(start: int, remain: int) -> None:
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(candidates)):
v = candidates[i]
if v > remain:
break
path.append(v)
dfs(i, remain - v)
path.pop()
dfs(0, target)
return ansvar combinationSum = function(candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start, remain) => {
if (remain === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
const v = candidates[i];
if (v > remain) break;
path.push(v);
dfs(i, remain - v);
path.pop();
}
};
dfs(0, target);
return ans;
};中文
题目概述
给定一组互不相同的正整数 candidates 和目标值 target，找出所有和为 target 的组合。每个数字可以被重复选择任意次。
核心思路
使用 DFS 回溯，并维护起始下标 start。当选择了 candidates[i] 后，下一层仍从 i 开始（允许重复使用同一数字），这样天然避免组合顺序重复。
暴力解法与不足
如果先盲目枚举所有可能多重集合再校验和，分支会爆炸。排序后利用 当前值 > 剩余值 立即剪枝，可以显著减少无效搜索。
最优算法步骤
1）先对 candidates 升序排序。
2）回溯状态为 (start, remain, path)。
3）若 remain == 0，把当前路径拷贝进答案。
4）从 start 到末尾枚举候选值。
5）若候选值大于 remain，直接 break。
6）加入当前值，递归到 (i, remain - value)，回溯时弹出。
复杂度分析
时间复杂度在最坏情况下是指数级（回溯枚举本质），但剪枝后实际表现通常更好。
空间复杂度为递归深度 O(target / minCandidate)，外加答案存储。
常见陷阱
- 选中数字后递归到 i + 1，会错误地禁止重复选同一个数字。
- 加入答案时忘记拷贝路径，导致结果被后续回溯污染。
- 不排序不剪枝，导致大量无效分支。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public java.util.List<java.util.List<Integer>> combinationSum(int[] candidates, int target) {
java.util.Arrays.sort(candidates);
java.util.List<java.util.List<Integer>> ans = new java.util.ArrayList<>();
dfs(candidates, 0, target, new java.util.ArrayList<>(), ans);
return ans;
}
private void dfs(int[] c, int start, int remain,
java.util.List<Integer> path,
java.util.List<java.util.List<Integer>> ans) {
if (remain == 0) {
ans.add(new java.util.ArrayList<>(path));
return;
}
for (int i = start; i < c.length; i++) {
if (c[i] > remain) break;
path.add(c[i]);
dfs(c, i, remain - c[i], path, ans);
path.remove(path.size() - 1);
}
}
}import "sort"
func combinationSum(candidates []int, target int) [][]int {
sort.Ints(candidates)
ans := [][]int{}
path := []int{}
var dfs func(start, remain int)
dfs = func(start, remain int) {
if remain == 0 {
comb := make([]int, len(path))
copy(comb, path)
ans = append(ans, comb)
return
}
for i := start; i < len(candidates); i++ {
v := candidates[i]
if v > remain {
break
}
path = append(path, v)
dfs(i, remain-v)
path = path[:len(path)-1]
}
}
dfs(0, target)
return ans
}class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> ans;
vector<int> path;
dfs(candidates, 0, target, path, ans);
return ans;
}
void dfs(const vector<int>& c, int start, int remain,
vector<int>& path, vector<vector<int>>& ans) {
if (remain == 0) {
ans.push_back(path);
return;
}
for (int i = start; i < (int)c.size(); ++i) {
if (c[i] > remain) break;
path.push_back(c[i]);
dfs(c, i, remain - c[i], path, ans);
path.pop_back();
}
}
};class Solution:
def combinationSum(self, candidates: list[int], target: int) -> list[list[int]]:
candidates.sort()
ans: list[list[int]] = []
path: list[int] = []
def dfs(start: int, remain: int) -> None:
if remain == 0:
ans.append(path.copy())
return
for i in range(start, len(candidates)):
v = candidates[i]
if v > remain:
break
path.append(v)
dfs(i, remain - v)
path.pop()
dfs(0, target)
return ansvar combinationSum = function(candidates, target) {
candidates.sort((a, b) => a - b);
const ans = [];
const path = [];
const dfs = (start, remain) => {
if (remain === 0) {
ans.push([...path]);
return;
}
for (let i = start; i < candidates.length; i++) {
const v = candidates[i];
if (v > remain) break;
path.push(v);
dfs(i, remain - v);
path.pop();
}
};
dfs(0, target);
return ans;
};
Comments