LeetCode77——Combinations

不念不忘少年蓝@ 2022-08-10 09:20 255阅读 0赞

LeetCode77——Combinations

题意：

两个数字n和k，找出所有这样的组合：

1.组合中有k个数字

2.组合是递增

3.组合中的数字是{1,2,3,….n} 的子集

为了叙述方便，假设子集为D，子集的大小为k。

那就是回溯了，对D中所有的数字进行k阶全排列，但这个全排列要排除非增序的组合。

代码：

class Solution {
private: 
    void help(int i,int n, int k,vector<int>temp,vector<vector<int>>&result)
    {
        if (temp.size() == k)//k个数
        {
            result.push_back(temp);
            return;
        }
        if (temp.size() > 1 && temp.back() < *(temp.end()-2))//递增
            return;
        for (int index = i+1; index < n+1; index++)//i
        {
            temp.push_back(index);
            help(index , n, k, temp, result);//递归
            temp.pop_back();//一次完成要弹出
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> temp;
        vector<vector<int>>result;
        help(0, n, k, temp, result);
        return result;
    }
};