题目描述
给定两个整数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 <= 201 <= k <= n
解决方案：
这段代码的核心功能是生成从 1 到 n 的数字中选取 k 个数字的所有组合（组合不考虑顺序，比如 n=4、k=2 时，输出[[4,3],[4,2],[4,1],[3,2],[3,1],[2,1]]），采用「回溯 + 剪枝」的思路实现，是组合问题的经典高效解法。
核心逻辑
成员变量作用：
path：临时数组，存储当前正在构造的组合（比如选取了 2 个数字时，path 可能是 [4,3]）；ans：最终结果数组，存储所有符合条件的 k 个数组合。
递归函数
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()删掉刚加入的数字，尝试下一个可选数字。
- 参数
主函数
combine：- 从数字上界
n开始调用dfs，启动组合构造过程； - 最终返回存储所有 k 数组合的
ans。
- 从数字上界
关键特点
- 剪枝优化：
n < k - len的判断是核心优化点，能大幅减少递归次数（比如 n=5、k=3，当前 path 长度为 1，还需选 2 个数，若剩余可选数字只有 1 个，直接终止）； - 去重逻辑：从大到小枚举数字，且下一轮只能选更小的数字，天然保证组合内数字递减，避免生成重复组合（组合不考虑顺序，此逻辑符合组合的定义）。
总结
- 核心思路：递归枚举可选数字，从大到小选数避免重复组合，通过剪枝提前终止无效递归，回溯遍历所有合法的 k 数组合；
- 关键操作：
path.push_back()（选数）和path.pop_back()（回溯）是遍历所有组合的核心，剪枝条件是提升效率的关键； - 功能效果：能输出 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; } };
