0077. 组合 [Medium] [Combinations].md

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

Example:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

---

题目：给定1 ... n共n个元素，返回所有包含了k个元素的组合，注意[2,4]和[4,2]算是同一种组合。

思路：回溯。类似216. Combination Sum III。当已经有k个元素时，无条件的回溯返回。

工程代码下载

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        if(n == 0 || k == 0) return res;
        vector<int> single;
        backtracking(res, single, n, k, 1);
        return res;
    }
private:
    void backtracking(vector<vector<int>>& res, vector<int>& single, const int& n, int k, int start){
        if(k==0){
            res.push_back(single);
        }

        for(int i=start; i<=n; ++i){
            single.push_back(i);
            //当前位置为i，寻找下一个位置（i+1）的元素
            backtracking(res, single, n, k-1, i+1);
            single.pop_back();
        }
    }
};