首页 > 代码库 > leetcode[77] Combinations

leetcode[77] Combinations

给定n和k,从1到n中选k个数,存到结果中。其实就是组合问题。例如

If n = 3, k = 2, 结果是 { 1,2], [1,3], [2,3] };

思路:利用回溯法。

class Solution {public:    void dfs77(vector<vector<int > > &ans, vector<int> subans, int start, int n, int k)    {        if (subans.size() == k)        {            ans.push_back(subans); return ;        }        for (int i = start; i <= n; i++)        {            subans.push_back(i);            dfs77(ans, subans, i + 1, n, k);            subans.pop_back(); // 满足一个条件或者该分支递归完后要删除最后一个        }    }    vector<vector<int> > combine(int n, int k) {        vector<vector<int > > ans;        if (n < k || k == 0) return ans;        vector<int> subans;        dfs77(ans, subans, 1, n, k);        return ans;    }};

 

leetcode[77] Combinations