LeetCode 77 Combinations组合全解四种回溯/位运算实现与源码级剖析【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文围绕 LeetCode 经典题77. Combinations组合完整讲解如何从1 ~ n中选出所有长度为k的组合覆盖四种解法两种回溯含/不含决策树、起始位置循环、迭代法以及位掩码法并提供 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 全语言实现。文章以 articles/combinations.md 为核心骨架结合本仓库 python/0077-combinations.py、java/0077-combinations.java、cpp/0077-combinations.cpp、go/0077-combinations.go 等源码进行印证。读完你将掌握组合枚举的通用模式、去重原理、复杂度推导与剪枝技巧并能直接迁移到全排列、子集、组合总和等一揽子回溯问题。前置知识Prerequisites在动手解决本题之前建议先熟悉以下四个基础模块递归Recursion理解如何把大问题拆成带基准条件base case的子问题回溯Backtracking掌握做出选择 → 深入探索 → 撤销选择的经典三段式套路位运算Bit Manipulation能用位掩码bitmask表示子集这是第四种解法的基石组合数学基础Combinatorics理解组合与排列的本质区别——组合不关心元素顺序[1,2]与[2,1]视为同一个结果。本题的结果数量为组合数公式 $\binom{n}{k} \frac{n!}{(n-k)! \cdot k!}$这是后续所有复杂度分析的基准。一、回溯法 I每个数字的取 / 不取决策树直觉Intuition对从1到n的每一个数字我们都面临一个二元选择把它加入当前组合或者跳过它。这样会形成一棵决策树树上的每一条从根到叶的路径都代表一个子集我们只保留最终大小为k的子集。这种写法与求子集问题的思路完全同构只是多了一个len k的过滤条件。算法Algorithm从空组合与索引i 1开始每一步有两个分支将当前数字i加入组合或跳过i递归处理两个分支索引前进为i 1当i n时到达叶子节点若当前组合恰好有k个元素则把它的副本加入结果集在探索跳过分支之前先回溯pop掉刚加入的元素。多语言实现Pythonclass Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] def backtrack(i, comb): if i n: if len(comb) k: res.append(comb.copy()) return comb.append(i) backtrack(i 1, comb) comb.pop() backtrack(i 1, comb) backtrack(1, []) return resJavapublic class Solution { private ListListInteger res; public ListListInteger combine(int n, int k) { res new ArrayList(); backtrack(1, n, k, new ArrayList()); return res; } private void backtrack(int i, int n, int k, ListInteger comb) { if (i n) { if (comb.size() k) { res.add(new ArrayList(comb)); } return; } comb.add(i); backtrack(i 1, n, k, comb); comb.remove(comb.size() - 1); backtrack(i 1, n, k, comb); } }Cclass Solution { vectorvectorint res; public: vectorvectorint combine(int n, int k) { vectorint comb; backtrack(1, n, k, comb); return res; } private: void backtrack(int i, int n, int k, vectorint comb) { if (i n) { if (comb.size() k) { res.push_back(comb); } return; } comb.push_back(i); backtrack(i 1, n, k, comb); comb.pop_back(); backtrack(i 1, n, k, comb); } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number[][]} */ combine(n, k) { const res []; const backtrack (i, comb) { if (i n) { if (comb.length k) { res.push([...comb]); } return; } comb.push(i); backtrack(i 1, comb); comb.pop(); backtrack(i 1, comb); }; backtrack(1, []); return res; } }C#public class Solution { public ListListint Combine(int n, int k) { ListListint res new ListListint(); void Backtrack(int i, Listint comb) { if (i n) { if (comb.Count k) { res.Add(new Listint(comb)); } return; } comb.Add(i); Backtrack(i 1, comb); comb.RemoveAt(comb.Count - 1); Backtrack(i 1, comb); } Backtrack(1, new Listint()); return res; } }Gofunc combine(n int, k int) [][]int { res : [][]int{} var backtrack func(i int, comb []int) backtrack func(i int, comb []int) { if i n { if len(comb) k { temp : make([]int, len(comb)) copy(temp, comb) res append(res, temp) } return } comb append(comb, i) backtrack(i1, comb) comb comb[:len(comb)-1] backtrack(i1, comb) } backtrack(1, []int{}) return res }Kotlinclass Solution { fun combine(n: Int, k: Int): ListListInt { val res mutableListOfListInt() fun backtrack(i: Int, comb: MutableListInt) { if (i n) { if (comb.size k) { res.add(ArrayList(comb)) } return } comb.add(i) backtrack(i 1, comb) comb.removeAt(comb.size - 1) backtrack(i 1, comb) } backtrack(1, mutableListOf()) return res } }Swiftclass Solution { func combine(_ n: Int, _ k: Int) - [[Int]] { var res [[Int]]() func backtrack(_ i: Int, _ comb: inout [Int]) { if i n { if comb.count k { res.append(comb) } return } comb.append(i) backtrack(i 1, comb) comb.removeLast() backtrack(i 1, comb) } var comb [Int]() backtrack(1, comb) return res } }Rustimpl Solution { pub fn combine(n: i32, k: i32) - VecVeci32 { let mut res Vec::new(); fn backtrack(i: i32, n: i32, k: i32, comb: mut Veci32, res: mut VecVeci32) { if i n { if comb.len() k as usize { res.push(comb.clone()); } return; } comb.push(i); backtrack(i 1, n, k, comb, res); comb.pop(); backtrack(i 1, n, k, comb, res); } backtrack(1, n, k, mut vec![], mut res); res } }复杂度分析时间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$即输出规模乘上每个组合的拷贝开销空间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$用于存放输出数组不包含递归栈本身。其中 $n$ 为元素总数$k$ 为每个组合要选取的元素个数。二、回溯法 II从起始位置顺序取数推荐写法直觉Intuition第二种回溯不做取/不取的二元决策而是遍历当前可选的数字并总是把当前数字加入组合。关键约束是递归进入下一层时起始位置设为i 1保证后续只能选更大的数字从而天然避免[1,2]与[2,1]这类重复。当组合长度达到k时立即停止。这一写法正是本仓库多语言源码实际采用的版本例如 python/0077-combinations.py 与 java/0077-combinations.java。算法Algorithm从空组合与起始索引1开始若组合大小等于k保存副本到结果并返回从start循环到n对每个数字i加入组合以start i 1递归调用只考虑比i更大的数字尝试下一个数字前弹出末尾元素完成回溯。多语言实现Pythonclass Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] def backtrack(start, comb): if len(comb) k: res.append(comb.copy()) return for i in range(start, n 1): comb.append(i) backtrack(i 1, comb) comb.pop() backtrack(1, []) return resJavapublic class Solution { private ListListInteger res; public ListListInteger combine(int n, int k) { res new ArrayList(); backtrack(1, n, k, new ArrayList()); return res; } private void backtrack(int start, int n, int k, ListInteger comb) { if (comb.size() k) { res.add(new ArrayList(comb)); return; } for (int i start; i n; i) { comb.add(i); backtrack(i 1, n, k, comb); comb.remove(comb.size() - 1); } } }Cclass Solution { public: vectorvectorint res; vectorvectorint combine(int n, int k) { res.clear(); vectorint comb; backtrack(1, n, k, comb); return res; } void backtrack(int start, int n, int k, vectorint comb) { if (comb.size() k) { res.push_back(comb); return; } for (int i start; i n; i) { comb.push_back(i); backtrack(i 1, n, k, comb); comb.pop_back(); } } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number[][]} */ combine(n, k) { const res []; const backtrack (start, comb) { if (comb.length k) { res.push([...comb]); return; } for (let i start; i n; i) { comb.push(i); backtrack(i 1, comb); comb.pop(); } }; backtrack(1, []); return res; } }C#public class Solution { public ListListint Combine(int n, int k) { ListListint res new ListListint(); void Backtrack(int start, Listint comb) { if (comb.Count k) { res.Add(new Listint(comb)); return; } for (int i start; i n; i) { comb.Add(i); Backtrack(i 1, comb); comb.RemoveAt(comb.Count - 1); } } Backtrack(1, new Listint()); return res; } }Gofunc combine(n int, k int) [][]int { res : [][]int{} var backtrack func(start int, comb []int) backtrack func(start int, comb []int) { if len(comb) k { temp : make([]int, len(comb)) copy(temp, comb) res append(res, temp) return } for i : start; i n; i { comb append(comb, i) backtrack(i1, comb) comb comb[:len(comb)-1] } } backtrack(1, []int{}) return res }Kotlinclass Solution { fun combine(n: Int, k: Int): ListListInt { val res mutableListOfListInt() fun backtrack(start: Int, comb: MutableListInt) { if (comb.size k) { res.add(ArrayList(comb)) return } for (i in start..n) { comb.add(i) backtrack(i 1, comb) comb.removeAt(comb.size - 1) } } backtrack(1, mutableListOf()) return res } }Swiftclass Solution { func combine(_ n: Int, _ k: Int) - [[Int]] { var res [[Int]]() func backtrack(_ start: Int, _ comb: inout [Int]) { if comb.count k { res.append(comb) return } for i in start...n { comb.append(i) backtrack(i 1, comb) comb.removeLast() } } var comb [Int]() backtrack(1, comb) return res } }Rustimpl Solution { pub fn combine(n: i32, k: i32) - VecVeci32 { let mut res Vec::new(); fn backtrack(start: i32, n: i32, k: i32, comb: mut Veci32, res: mut VecVeci32) { if comb.len() k as usize { res.push(comb.clone()); return; } for i in start..n { comb.push(i); backtrack(i 1, n, k, comb, res); comb.pop(); } } backtrack(1, n, k, mut vec![], mut res); res } }复杂度分析时间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$空间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$用于存放输出数组。其中 $n$ 为元素总数$k$ 为每个组合要选取的元素个数。仓库源码印证仓库中的实现与本文第二种写法保持一致。以 python/0077-combinations.py 为例class Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] def helper(start, comb): if len(comb) k: res.append(comb.copy()) return for i in range(start, n1): comb.append(i) helper(i1, comb) comb.pop() helper(1, []) return res值得注意的细节comb.copy()保证存入结果的是独立副本Java 版本 java/0077-combinations.java 在回溯时使用comb.remove((Integer) i)按值删除避免remove(int)重载误删索引位置C 版本 cpp/0077-combinations.cpp 通过vectorint引用传递并pop_back()撤销选择。三、迭代法用指针模拟递归栈直觉Intuition回溯的递归调用本质上是在维护一棵搜索树。我们可以用一个大小为k的数组来存放当前组合用一个位置指针i模拟递归深度找到合法数字时指针前进需要回退时指针后退。这种方式消除了递归调用本身的栈开销。算法Algorithm初始化长度为k的全零数组comb与指针i 0将comb[i]自增尝试位置i的下一个候选值若comb[i] n指针回退i - 1实现回溯若i k - 1说明已经填满k个位置保存当前组合否则指针前进i 1并令comb[i] comb[i - 1]保证下一位置从上一个位置的后续值开始保持严格递增重复直到i 0此时所有组合已枚举完毕。多语言实现Pythonclass Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] i 0 comb [0] * k while i 0: comb[i] 1 if comb[i] n: i - 1 continue if i k - 1: res.append(comb.copy()) else: i 1 comb[i] comb[i - 1] return resJavapublic class Solution { public ListListInteger combine(int n, int k) { ListListInteger res new ArrayList(); int[] comb new int[k]; int i 0; while (i 0) { comb[i]; if (comb[i] n) { i--; continue; } if (i k - 1) { ListInteger current new ArrayList(); for (int num : comb) { current.add(num); } res.add(current); } else { i; comb[i] comb[i - 1]; } } return res; } }Cclass Solution { public: vectorvectorint combine(int n, int k) { vectorvectorint res; vectorint comb(k, 0); int i 0; while (i 0) { comb[i]; if (comb[i] n) { i--; continue; } if (i k - 1) { res.push_back(comb); } else { i; comb[i] comb[i - 1]; } } return res; } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number[][]} */ combine(n, k) { const res []; const comb Array(k).fill(0); let i 0; while (i 0) { comb[i]; if (comb[i] n) { i--; continue; } if (i k - 1) { res.push([...comb]); } else { i; comb[i] comb[i - 1]; } } return res; } }C#public class Solution { public ListListint Combine(int n, int k) { ListListint res new ListListint(); int[] comb new int[k]; int i 0; while (i 0) { comb[i]; if (comb[i] n) { i--; continue; } if (i k - 1) { res.Add(new Listint(comb)); } else { i; comb[i] comb[i - 1]; } } return res; } }Gofunc combine(n int, k int) [][]int { res : [][]int{} comb : make([]int, k) i : 0 for i 0 { comb[i] if comb[i] n { i-- continue } if i k-1 { temp : make([]int, k) copy(temp, comb) res append(res, temp) } else { i comb[i] comb[i-1] } } return res }Kotlinclass Solution { fun combine(n: Int, k: Int): ListListInt { val res mutableListOfListInt() val comb IntArray(k) var i 0 while (i 0) { comb[i] if (comb[i] n) { i-- continue } if (i k - 1) { res.add(comb.toList()) } else { i comb[i] comb[i - 1] } } return res } }Swiftclass Solution { func combine(_ n: Int, _ k: Int) - [[Int]] { var res [[Int]]() var comb Int var i 0 while i 0 { comb[i] 1 if comb[i] n { i - 1 continue } if i k - 1 { res.append(comb) } else { i 1 comb[i] comb[i - 1] } } return res } }Rustimpl Solution { pub fn combine(n: i32, k: i32) - VecVeci32 { let k k as usize; let mut res Vec::new(); let mut comb vec![0i32; k]; let mut i: i32 0; while i 0 { comb[i as usize] 1; if comb[i as usize] n { i - 1; continue; } if i as usize k - 1 { res.push(comb.clone()); } else { let prev comb[i as usize]; i 1; comb[i as usize] prev; } } res } }复杂度分析时间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$空间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$用于存放输出数组。其中 $n$ 为元素总数$k$ 为每个组合要选取的元素个数。四、位运算用位掩码枚举子集直觉Intuition1 ~ n的任意一个子集都可以用一个n位二进制数表示第i位为1表示数字i1被选中。遍历0 ~ 2^n - 1的所有掩码只保留恰好有k个二进制位为1的掩码即可得到全部组合。该思路适合n较小的场景如n ≤ 20因为枚举量是2^n指数级。算法Algorithm从0遍历到2^n - 1每个整数mask代表一个可能的子集对每个掩码提取所有置位位对应的数字若第j位为1则加入j 1若提取出的子集恰好有k个元素则加入结果集返回全部合法组合。多语言实现Pythonclass Solution: def combine(self, n: int, k: int) - List[List[int]]: res [] for mask in range(1 n): comb [] for bit in range(n): if mask (1 bit): comb.append(bit 1) if len(comb) k: res.append(comb) return resJavapublic class Solution { public ListListInteger combine(int n, int k) { ListListInteger res new ArrayList(); for (int mask 0; mask (1 n); mask) { ListInteger comb new ArrayList(); for (int bit 0; bit n; bit) { if ((mask (1 bit)) ! 0) { comb.add(bit 1); } } if (comb.size() k) { res.add(comb); } } return res; } }Cclass Solution { public: vectorvectorint combine(int n, int k) { vectorvectorint res; for (int mask 0; mask (1 n); mask) { vectorint comb; for (int bit 0; bit n; bit) { if (mask (1 bit)) { comb.push_back(bit 1); } } if (comb.size() k) { res.push_back(comb); } } return res; } };JavaScriptclass Solution { /** * param {number} n * param {number} k * return {number[][]} */ combine(n, k) { const res []; for (let mask 0; mask 1 n; mask) { if (mask.toString(2).split(1).length - 1 ! k) { continue; } const comb []; for (let bit 0; bit n; bit) { if (mask (1 bit)) { comb.push(bit 1); } } res.push(comb); } return res; } }C#public class Solution { public ListListint Combine(int n, int k) { ListListint res new ListListint(); for (int mask 0; mask (1 n); mask) { Listint comb new Listint(); for (int bit 0; bit n; bit) { if ((mask (1 bit)) ! 0) { comb.Add(bit 1); } } if (comb.Count k) { res.Add(comb); } } return res; } }Gofunc combine(n int, k int) [][]int { res : [][]int{} for mask : 0; mask (1 n); mask { comb : []int{} for bit : 0; bit n; bit { if mask(1bit) ! 0 { comb append(comb, bit1) } } if len(comb) k { res append(res, comb) } } return res }Kotlinclass Solution { fun combine(n: Int, k: Int): ListListInt { val res mutableListOfListInt() for (mask in 0 until (1 shl n)) { val comb mutableListOfInt() for (bit in 0 until n) { if (mask and (1 shl bit) ! 0) { comb.add(bit 1) } } if (comb.size k) { res.add(comb) } } return res } }Swiftclass Solution { func combine(_ n: Int, _ k: Int) - [[Int]] { var res [[Int]]() for mask in 0..(1 n) { var comb [Int]() for bit in 0..n { if mask (1 bit) ! 0 { comb.append(bit 1) } } if comb.count k { res.append(comb) } } return res } }Rustimpl Solution { pub fn combine(n: i32, k: i32) - VecVeci32 { let mut res Vec::new(); for mask in 0..(1 n) { let mut comb Vec::new(); for bit in 0..n { if mask (1 bit) ! 0 { comb.push(bit 1); } } if comb.len() k as usize { res.push(comb); } } res } }复杂度分析时间复杂度$O(n \cdot 2^n)$——遍历全部2^n个掩码每个掩码最多扫描n位空间复杂度$O(k \cdot \frac{n!}{(n-k)! \cdot k!})$用于存放输出数组。其中 $n$ 为元素总数$k$ 为每个组合要选取的元素个数。五、剪枝优化提前终止无效分支回溯法 II 存在一个明显的冗余当剩余可选的数字不足以填满k个位置时继续递归没有意义。以 go/0077-combinations.go 为例仓库在循环上界上做了经典剪枝func backtrack(n, k, start int, arr []int, ans *[][]int) { if len(arr) k { comb : make([]int, k) copy(comb, arr) *ans append(*ans, comb) return } for i : start; i n-k(len(arr)1); i { arr append(arr, i) backtrack(n, k, i1, arr, ans) arr arr[:len(arr)-1] } }推导过程当前组合已有len(arr)个元素还需要k - len(arr)个元素若从i开始到n的可选数量n - i 1小于所需数量k - len(arr)则此分支永远无法凑满k个可以直接剪掉。因此循环上界为i ≤ n - (k - len(arr)) 1 n - k len(arr) 1。这一优化将循环范围从start..n收窄为start..n-klen(arr)1可以显著减少无效递归调用。六、常见陷阱Common Pitfalls陷阱一加入结果前忘记拷贝组合把当前组合加入结果集时必须创建副本。否则后续回溯过程中的修改会污染已经存入的结果。# 错误存入的是引用后续修改会连带改变已加入的结果 res.append(comb) # 正确存入副本 res.append(comb.copy())这正是各语言实现中使用comb.copy()Python、new ArrayList(comb)Java、[...comb]JavaScript、comb.clone()Rust的原因。陷阱二缺少回溯撤销步骤在探索完包含某元素的分支后必须先把该元素移除再探索下一个分支。遗漏pop会导致组合元素数量膨胀、结果大量重复。comb.append(i) backtrack(i 1, comb) # 缺失comb.pop()陷阱三循环起点写错如果把循环起点写成0或start - 1而不是start就会产生[1,2]与[2,1]这类重复组合。循环必须从当前起始位置开始保证每个组合只按升序生成一次。七、四种解法横向对比解法核心思想时间复杂度空间复杂度适用场景回溯 I取/不取决策树枚举所有子集再过滤大小$O(k \cdot \binom{n}{k})$$O(k \cdot \binom{n}{k})$思路直观与子集问题统一回溯 II起始位置循环递增起点保证无重复$O(k \cdot \binom{n}{k})$$O(k \cdot \binom{n}{k})$面试首选配合剪枝更优迭代法指针模拟数组 指针模拟递归栈$O(k \cdot \binom{n}{k})$$O(k \cdot \binom{n}{k})$避免递归调用栈开销位运算位掩码二进制位表示子集$O(n \cdot 2^n)$$O(k \cdot \binom{n}{k})$仅适合n较小的场景其中 $\binom{n}{k} \frac{n!}{(n-k)! \cdot k!}$。实际面试与竞赛中回溯 II 剪枝是最推荐的组合既有清晰的递归结构又能通过上界收窄减少无效分支。八、延伸从组合到回溯问题家族掌握组合枚举后可以自然迁移到仓库中的一系列同类回溯问题组合总和Combination Sum元素可重复使用不再固定k而是固定目标和对应源码 python/0039-combination-sum.py组合总和 IICombination Sum II每个元素只能用一次且需去重对应源码 python/0040-combination-sum-ii.py组合总和 IVCombination Sum IV求方案数且顺序相关本质是动态规划对应源码 python/0377-combination-sum-iv.py电话号码的字母组合不同位置的可选集合不同对应源码 python/0017-letter-combinations-of-a-phone-number.py全排列Permutations 与 子集Subsets分别使用used数组标记访问与不限制长度的组合枚举。它们共享同一条选择 → 递归 → 撤销的主线区别只在于候选集、终止条件与去重手段的不同。总结LeetCode 77 是回溯算法最经典的入门题本仓库 articles/combinations.md 给出了四种完整解法与九种语言实现。核心要点可归纳为三条选择与撤销对称append与pop必须成对出现这是回溯正确性的根基用递增起点去重递归时传i 1保证组合内严格递增天然避免排列式重复副本入结果存入结果集时务必拷贝否则回溯会破坏已保存的组合。建议在 python/0077-combinations.py 等源码基础上自行实现剪枝版本并跑通n4, k2输出 6 个组合与n5, k3输出 10 个组合两组用例即可彻底掌握组合类回溯问题的通用解法。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
