Posted on 2014-01-19 01:36
Uriel 阅读(155)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
从1-n中取k个数输出所有取法, 就是求组合数啦,还是DFS,跟Subsets II方法一样,但是还是调了一会。。每次写递归脑袋就发晕。。这么多年不曾改变。。简直。。
1 class Solution {
2 public:
3 vector<vector<int>> res;
4 int nt;
5
6 void DFS(int n, int k, vector<int> &tp, int pos) {
7 if(nt == k) {
8 res.push_back(tp);
9 return;
10 }
11 for(int i = pos; i <= n; ++i) {
12 tp.push_back(i);
13 nt++;
14 DFS(n, k, tp, i + 1);
15 tp.pop_back();
16 nt--;
17 }
18 }
19
20 vector<vector<int> > combine(int n, int k) {
21 vector<int> tp;
23 res.clear();
24 nt = 0;
25 DFS(n, k, tp, 1);
26 return res;
27 }
28 };