算法思路

在DFS求子集总结 中已经详细介绍了求子集的过程，其实这道题本质上也是一个求子集的问题。题目给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。其实就是求由1 ~ n的数字组成集合的子集，并且子集的个数刚好是k的所有子集方案。因此我们可以在求子集的同时再添加一个参数s,来表示当前该子集中的元素个数，当个数刚好为k时，即可加入方案，具体代码实现如下：

C ++代码

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

    vector<vector<int>> combine(int n, int k) {
        dfs(n, 1, 0, k);
        return res;    
    }

    void dfs(int n, int u, int s, int k)
    {
        if (s == k) //该子集个数恰好为k
        {
            res.push_back(path); //添加方案
            return;
        }

        if (u > n) return; //说明已经遍历完所有数，但是子集大小不足k
        path.push_back(u); //选当前数
        dfs(n, u + 1, s + 1, k); //子集个数s+1
        path.pop_back(); //回溯
        dfs(n, u + 1, s, k); //不选当前数，子集个数s不变
    }
};