LeetCode77. Combinations(剑指offer38-2)

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],

]

回溯法。

细节。循环i=start;i++和递归的(i+1)的意义。

class Solution {

public:

    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> ret;

        vector<int> out;

        Helper(n,k,ret,out,1);

        return ret;

    }

    void Helper(int n, int k ,vector<vector<int>> &ret,vector<int>& out,int start)

    {

        if(out.size()==k)

        {

            ret.push_back(out);

            return;

        }

        for(int i = start;i<=n;i++)

        {

            out.push_back(i);

            Helper(n,k,ret,out,i+1); //开始下级，从i的后面开始。因为是组合不是排列，所以之前取过的数就不取了

            out.pop_back();//一次回溯

        }

    }

};

法2. C(n, k) = C(n-1, k-1) + C(n-1, k)，

把n个元素分成两组，第一组n-1个，第二组1个

从中取出k个元素【方法有 C(n，k)种】，取法有两种

(1)从第一组中取出k个方法有C(n-1，k)种

(2) 从第一组中取出k-1个，从第二组中取出1个方法有C(n-1，k-1)种

class Solution {

public:

    vector<vector<int>> combine(int n, int k) {

        if(n<k||k<0) return {};

        if(k==0) return {{}};

        //保存从n-1里面选k-1个的结果res.再在res中每个数组末尾加最后一个数(n)

        vector<vector<int>> res=combine(n-1,k-1);

        for(auto &a:res) a.push_back(n);

        //保存从n-1里面选k个的结果。将结果中的每个数组都push进res结果集里。

        for(auto a:combine(n-1,k)) res.push_back(a);

        return res;

    }

};

巴特西

LeetCode77. Combinations(剑指offer38-2)

最新文章

热门文章