Posted on 2014-01-19 01:36
Uriel 閱讀(174)
評論(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 };