Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Combinations

Leetcode algorithms 第 77 题: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],
]

解答

n个数选择k个的所有组合,直接使用递归算法解决。递归时每次从最后元素开始选择,记录下次可以选择的最大元素,当选完k次时即可得到一个答案。

具体代码如下:

class Solution {
public:
    void f(int n, int k, vector<int> &v, vector<vector<int> > &ans)
    { //当前可以选择的最大数,剩余元素个数,当前选择,答案
        if (k == 0) //选完了
        {
            vector<int> tem = v;
            sort(tem.begin(), tem.end());
            ans.push_back(tem);
            return;
        }
        for (int i = n; i > 0; i--) //选择一个
        {
            v.push_back(i);
            f(i-1, k-1, v, ans);
            v.pop_back(); //回溯
        }
    }
    
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> > ans;
        vector<int> v;
        f(n, k, v, ans);
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论