描述

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

思路

这道题和第39题.组合总和差不多，比39题还简单，在39的基础上改动一下代码就可以了。这道题本质上也是求1～n的全排列，结果中不包含自身的全排列。不多赘述，回溯算法的代码一看就懂。

解答

class Solution {
public:
vector<vector<int> > res;
vector<int> v_tmp;
int K, N;
    vector<vector<int>> combine(int n, int k) {
        N = n;
        K = k;
        backTrack(1);
        return res;
    }
    void backTrack(int start){
        if(v_tmp.size() == K){
            res.push_back(v_tmp);
            return;
        }
        for(int i = start;i <= N; ++ i){
            v_tmp.push_back(i);
            backTrack(i+1);
            v_tmp.pop_back();
        }
    }
};