生成1-n选k个数的所有组合，DFS
C++
1 //77
2 //Runtime 48 ms (Beats 24.56%)
3
4 class Solution {
5 public:
6 vector<vector<int>> res;
7 int nt;
8
9 void DFS(int n, int k, vector<int> &tp, int pos) {
10 if(nt == k) {
11 res.push_back(tp);
12 return;
13 }
14 for(int i = pos; i <= n; ++i) {
15 tp.push_back(i);
16 nt++;
17 DFS(n, k, tp, i + 1);
18 tp.pop_back();
19 nt--;
20 }
21 }
22
23 vector<vector<int> > combine(int n, int k) {
24 vector<int> tp;
25 //sort(S.begin(), S.end());
26 res.clear();
27 nt = 0;
28 DFS(n, k, tp, 1);
29 return res;
30 }
31 };
Python
1 #77
2 #Runtime: 340 ms (Beats 77%)
3 #Memory: 14.9 MB (Beats 55.68%)
4
5 class Solution(object):
6 def combine(self, n, k):
7 """
8 :type n: int
9 :type k: int
10 :rtype: List[List[int]]
11 """
12 self.ans = []
13 def dfs(tp, p):
14 if len(tp) == k:
15 self.ans.append(tp[:])
16 return
17 for i in range(p, n + 1):
18 tp.append(i)
19 dfs(tp, i + 1)
20 tp.pop()
21 dfs([], 1)
22 return self.ans