目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Combinations - LeetCode

注意点

解法

解法一：递归，如果tmp中有k个数字就把tmp加到ret中，否则继续往tmp添加数字。

class Solution {
public:
    void recursion(int n,int k,int start,vector<int> tmp,vector<vector<int>>& ret)
    {
        if(tmp.size() == k) 
        {
            ret.push_back(tmp);
            return;
        }
        int i;
        for(i = start;i <= n;i++)
        {
            tmp.push_back(i);
            recursion(n,k,i+1,tmp,ret);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        vector<int> tmp;
        recursion(n,k,1,tmp,ret);
        return ret;
    }
};

解法二：非递归，如果tmp中有k个数字就把tmp加到ret中，否则继续往tmp添加数字。

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> >ret;
        vector<vector<int> >vec(1);
        for(int i = 1; i <= n; i++)
        {
            int len = vec.size();
            vector<int> tmp;
            for(int j = 0; j < len; j++)
            {
                tmp = vec[j];
                tmp.push_back(i);
                if(tmp.size() == k)ret.push_back(tmp);
                else vec.push_back(tmp);
            }
        }
        return ret;
    }
};

小结

• 怎么都这么耗时呢