您当前位置：首页 > php框架 > 框架设计 > leetcode || 77、Combinations

leetcode || 77、Combinations

来源：程序员人生发布时间：2015-04-17 08:44:13 阅读次数：3050次

problem：

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

Hide Tags

Backtracking

题意：输出1~n的 k 个数字的所有排列组合

thinking：

（1）看到题就应想到用DFS深搜法

（2）深搜的难点在于下1步怎样处理，这里开1个K大小的数组，记录深搜的每步获得的数字

（3）时间复杂度为O（K*N），空间复杂度为O（k）

code：

class Solution { private: vector<vector<int> > ret; vector<int> tmp; public: vector<vector<int> > combine(int n, int k) { ret.clear(); tmp.resize(k); dfs(1,n,k,1); return ret; } protected: void dfs(int dep, int n, int k,int start) { if(dep>k) { ret.push_back(tmp); return; } for(int i=start;i<=n;i++) { tmp[dep⑴]=i; dfs(dep+1,n,k,i+1); } } };

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 23种设计模式汇总整理

下一篇 求解最大公约数和最小公倍数问题

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点