LeetCode 77: Combinations (Backtracking with Pruning)
LeetCode 77BacktrackingCombinatoricsInterviewToday we solve LeetCode 77 - Combinations.
Source: https://leetcode.com/problems/combinations/
English
Problem Summary
Given two integers n and k, return all possible combinations of k numbers chosen from [1..n].
Key Insight
Build combinations in ascending order using DFS. At position start, if we still need need = k - path.size() numbers, then the current candidate i only needs to loop to n - need + 1. This pruning avoids useless branches.
Brute Force and Limitations
Brute force would enumerate all subsets of [1..n] and keep those with size k, which explores many irrelevant states. Direct backtracking constructs only valid-length paths.
Optimal Algorithm Steps
1) Maintain path as current partial combination.
2) If path.size() == k, append a copy to answer.
3) Let need = k - path.size(), iterate i from start to n - need + 1.
4) Choose i, recurse with i + 1, then backtrack.
Complexity Analysis
Time: O(C(n,k) * k) (copying each combination costs k).
Space: O(k) recursion depth (excluding output).
Common Pitfalls
- Forgetting to copy path before pushing to answer.
- Missing pruning upper bound, causing extra recursion.
- Using non-ascending picks and generating duplicates.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private final List<List<Integer>> ans = new ArrayList<>();
private final List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
private void dfs(int start, int n, int k) {
if (path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}
int need = k - path.size();
int upper = n - need + 1;
for (int i = start; i <= upper; i++) {
path.add(i);
dfs(i + 1, n, k);
path.remove(path.size() - 1);
}
}
}func combine(n int, k int) [][]int {
ans := make([][]int, 0)
path := make([]int, 0, k)
var dfs func(start int)
dfs = func(start int) {
if len(path) == k {
comb := append([]int(nil), path...)
ans = append(ans, comb)
return
}
need := k - len(path)
upper := n - need + 1
for i := start; i <= upper; i++ {
path = append(path, i)
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(1)
return ans
}class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
void dfs(int start, int n, int k) {
if ((int)path.size() == k) {
ans.push_back(path);
return;
}
int need = k - (int)path.size();
int upper = n - need + 1;
for (int i = start; i <= upper; ++i) {
path.push_back(i);
dfs(i + 1, n, k);
path.pop_back();
}
}
};class Solution:
def combine(self, n: int, k: int) -> list[list[int]]:
ans = []
path = []
def dfs(start: int) -> None:
if len(path) == k:
ans.append(path.copy())
return
need = k - len(path)
upper = n - need + 1
for x in range(start, upper + 1):
path.append(x)
dfs(x + 1)
path.pop()
dfs(1)
return ansvar combine = function(n, k) {
const ans = [];
const path = [];
const dfs = (start) => {
if (path.length === k) {
ans.push([...path]);
return;
}
const need = k - path.length;
const upper = n - need + 1;
for (let i = start; i <= upper; i++) {
path.push(i);
dfs(i + 1);
path.pop();
}
};
dfs(1);
return ans;
};中文
题目概述
给定整数 n 和 k，返回从 [1..n] 中选取 k 个数字的所有组合。
核心思路
用回溯按递增顺序构造组合。若当前路径长度为 len，还需要 need = k - len 个数，那么当前层起点为 start 时，枚举上界可以直接剪枝到 n - need + 1。
暴力解法与不足
暴力法会先枚举全部子集再筛选长度为 k 的结果，搜索空间更大。回溯法直接生成合法长度路径，更高效也更直观。
最优算法步骤
1）维护当前路径 path。
2）当 path.size()==k 时，将副本加入答案。
3）计算 need，枚举 i 从 start 到 n - need + 1。
4）选择 i 递归下一层，返回后回溯。
复杂度分析
时间复杂度：O(C(n,k) * k)（每个组合拷贝一次）。
空间复杂度：O(k)（不含输出结果）。
常见陷阱
- 把 path 直接放入答案，导致后续回溯污染结果。
- 忘记剪枝上界，递归分支过多。
- 不按递增顺序选择，容易产生重复组合。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private final List<List<Integer>> ans = new ArrayList<>();
private final List<Integer> path = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
private void dfs(int start, int n, int k) {
if (path.size() == k) {
ans.add(new ArrayList<>(path));
return;
}
int need = k - path.size();
int upper = n - need + 1;
for (int i = start; i <= upper; i++) {
path.add(i);
dfs(i + 1, n, k);
path.remove(path.size() - 1);
}
}
}func combine(n int, k int) [][]int {
ans := make([][]int, 0)
path := make([]int, 0, k)
var dfs func(start int)
dfs = func(start int) {
if len(path) == k {
comb := append([]int(nil), path...)
ans = append(ans, comb)
return
}
need := k - len(path)
upper := n - need + 1
for i := start; i <= upper; i++ {
path = append(path, i)
dfs(i + 1)
path = path[:len(path)-1]
}
}
dfs(1)
return ans
}class Solution {
public:
vector<vector<int>> ans;
vector<int> path;
vector<vector<int>> combine(int n, int k) {
dfs(1, n, k);
return ans;
}
void dfs(int start, int n, int k) {
if ((int)path.size() == k) {
ans.push_back(path);
return;
}
int need = k - (int)path.size();
int upper = n - need + 1;
for (int i = start; i <= upper; ++i) {
path.push_back(i);
dfs(i + 1, n, k);
path.pop_back();
}
}
};class Solution:
def combine(self, n: int, k: int) -> list[list[int]]:
ans = []
path = []
def dfs(start: int) -> None:
if len(path) == k:
ans.append(path.copy())
return
need = k - len(path)
upper = n - need + 1
for x in range(start, upper + 1):
path.append(x)
dfs(x + 1)
path.pop()
dfs(1)
return ansvar combine = function(n, k) {
const ans = [];
const path = [];
const dfs = (start) => {
if (path.length === k) {
ans.push([...path]);
return;
}
const need = k - path.length;
const upper = n - need + 1;
for (let i = start; i <= upper; i++) {
path.push(i);
dfs(i + 1);
path.pop();
}
};
dfs(1);
return ans;
};
Comments