首页 > 代码库 > [leetcode] Combinations

[leetcode] 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],]
思路:
dfs搜索所有可行解。这里[1,2]和[2,1]算一个解,所以后面的数一定越来越大。
题解:
class Solution {public:    vector<vector<int> > res;    vector<int> tmp;    void dfs(int n, int k, int t) {        if(k==0) {            res.push_back(tmp);            return;        }        for(int i=t+1;i<=n;i++) {            tmp.push_back(i);            dfs(n,k-1,i);            tmp.pop_back();        }    }    vector<vector<int> > combine(int n, int k) {        if(k==0)            return res;        for(int i=1;i<=n;i++) {            tmp.push_back(i);            dfs(n,k-1,i);            tmp.pop_back();        }        return res;    }};

 

 

[leetcode] Combinations