题目内容

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

示例

示例:

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

题解

本题考查深度优先搜索算法。

由于在n个数中依次选择k个，因此需要考虑选择重复的问题，类似先选择1后选2与先选2后选1的方式其实本质相同。

故而，我们需要确定一个机制，即不重复的机制。这里，我给出一个机制：即选择的顺序一定是先从前面选，然后选择此数后面的数字。类似先选择1后选择3，不能先选择3，再选择1；当选择3时，后面的数只能选择比3大的数。

在定义dfs函数的参数有：一共n个数，当前选择了u个数，start从哪个位置开始选择。

具体，请看代码。

代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> combine(int n, int k) {
        dfs(n,k,1);
        return res;
    }   
    void dfs(int n, int k, int start){
        //n代表选择范围，u代表选了第几个数，start代表从哪个数开始选
        if(!k){
            //当选择了k个数之后，添加方案并返回
            res.push_back(path);
            return;
        }
        for(int i = start; i <= n; i++){
            path.push_back(i);
            dfs(n, k - 1, i + 1);
            path.pop_back();
        }
    }
};