day155—回溯—组合（LeetCode-77）

题目描述

给定两个整数n和k，返回范围[1, n]中所有可能的k个数的组合。

你可以按任何顺序返回答案。

示例 1：

输入：n = 4, k = 2输出：[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

示例 2：

输入：n = 1, k = 1输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

解决方案：

这段代码的核心功能是生成从 1 到 n 的数字中选取 k 个数字的所有组合（组合不考虑顺序，比如 n=4、k=2 时，输出[[4,3],[4,2],[4,1],[3,2],[3,1],[2,1]]），采用「回溯 + 剪枝」的思路实现，是组合问题的经典高效解法。

核心逻辑

1. 成员变量作用：

   • path：临时数组，存储当前正在构造的组合（比如选取了 2 个数字时，path 可能是 [4,3]）；
   • ans：最终结果数组，存储所有符合条件的 k 个数组合。

2. 递归函数dfs逻辑：

   • 参数n：当前可选数字的上界（只能从1~n中选数）；k：需要选取的数字个数；
   • 剪枝条件（提前终止无效递归）：if(n < k - len)—— 剩余可选数字个数（n）小于 “还需要选的数字个数（k-len）”，说明不可能凑够 k 个数，直接返回，避免无效递归；
   • 终止条件：if(len == k)—— 当前组合的长度等于 k，说明已选够 k 个数，将path加入ans后返回；
   • 核心流程（从大到小枚举 + 回溯）：① 遍历从n到1的所有数字i（从大到小选，避免重复组合，比如不会同时出现 [3,4] 和 [4,3]）；② 选数字i：将i加入path，递归调用dfs(i-1, k)（下一轮只能从1~i-1中选数，保证组合内数字递减，无重复）；③ 回溯：递归返回后，执行path.pop_back()删掉刚加入的数字，尝试下一个可选数字。

3. 主函数combine：

   • 从数字上界n开始调用dfs，启动组合构造过程；
   • 最终返回存储所有 k 数组合的ans。

关键特点

• 剪枝优化：n < k - len的判断是核心优化点，能大幅减少递归次数（比如 n=5、k=3，当前 path 长度为 1，还需选 2 个数，若剩余可选数字只有 1 个，直接终止）；
• 去重逻辑：从大到小枚举数字，且下一轮只能选更小的数字，天然保证组合内数字递减，避免生成重复组合（组合不考虑顺序，此逻辑符合组合的定义）。

总结

1. 核心思路：递归枚举可选数字，从大到小选数避免重复组合，通过剪枝提前终止无效递归，回溯遍历所有合法的 k 数组合；
2. 关键操作：path.push_back()（选数）和path.pop_back()（回溯）是遍历所有组合的核心，剪枝条件是提升效率的关键；
3. 功能效果：能输出 1~n 中选 k 个数的所有组合，无重复、无遗漏，且效率高于无剪枝的暴力枚举。

以 n=4、k=2 为例，最终会生成所有 2 数组合：[[4,3],[4,2],[4,1],[3,2],[3,1],[2,1]]，符合组合的定义（不考虑顺序）。

函数源码：

class Solution { public: vector<int>path={}; vector<vector<int>>ans={}; void dfs(int n,int k){ int len=path.size(); if(n<k-len){ return; } if(len==k){ ans.push_back(path); return; } for(int i=n;i>0;i--){ path.push_back(i); dfs(i-1,k); path.pop_back(); } } vector<vector<int>> combine(int n, int k) { dfs(n,k); return ans; } };