077–Combinations

Combinations

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

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Hide Tags

Backtracking

Hide Similar Problems

(M) Combination Sum (M) Permutations

用bfs做的，依次取值罗列所有组合。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> rst;
        vector<int> group;
        if(k&&k<=n)
            build(rst, group, 1, n, k-1);
        return rst;
    }
private:
    void build(vector<vector<int>>& rst, vector<int>& group, int begin, int n, int k)
    {
        for(int ii=begin; ii<=n; ++ii)
        {
            group.push_back(ii);
            if(!k)
                rst.push_back(group);
            else
                build(rst, group, ii+1, n, k-1);
            group.pop_back();
        }
        return;
    }
};

12 ms.