🤷‍♀️ 题目：

给定两个整数 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]]

😊 解题：

分析：

对于区间内的每一个数 cur ，当我们询问到 cur 这个位置的时候，区间[1, cur-1] 中所有的数的选择状态一定是确定的，我们只需要考虑当前 cur 这个数选或者不选。如果选的话，将 cur 加入到临时的答案数组temp中，然后去查询 [cur + 1, n], 如果不取的话，就直接查询 [cur + 1, n] 。如果临时的答案数组 ans 的长度等于 k ，那么就说明找到了一种合适的排列，将其保存下来，然后进行回溯即可。
优化：如果递归的过程中发现，当前答案数组的长度加上剩余区间的长度还是小于目标序列的长度的话，那么我们就可以直接递归返回，因为无论怎么排列，最终都不可以得到合适的排列（长度不满足条件）

代码：

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> number;
    void dfs(int cur,int n,int k){ // 总共n个数，组成k个数
        if(number.size() + (n- cur + 1 ) < k){
            return;
        }
        if(number.size() == k){
            ans.push_back(number);
            return;
        }
        number.push_back(cur);
        dfs(cur+1,n,k);
        number.pop_back();
        dfs(cur+1,n,k);
    }
    vector<vector<int>> combine(int n, int k) {
        dfs(1,n,k);
        return ans;
    }
};