国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php框架 > 框架设计 > leetcode || 77、Combinations

leetcode || 77、Combinations

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

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); } } };


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