1.题目描述
给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 示例:
2.回溯法
比如输入 n = 4, k = 2，输出如下结果，顺序无所谓，但是不能包含重复（按照组合的定义，[1,2] 和 [2,1] 也算重复）： [ [1,2], [1,3], [1,4], [2,3], [2,4], [3,4] ] k 限制了树的高度，n 限制了树的宽度
3.代码
class Solution {
public:
vector
<vector
<int>> combine(int n
, int k
) {
vector
<vector
<int>> res
;
if(n
<= 0 || k
<= 0){
return res
;
}
vector
<int> track
;
backTrack(track
, res
, n
, k
, 1);
return res
;
}
void backTrack(vector
<int>& track
, vector
<vector
<int>>& res
, int n
, int k
, int start
){
if(track
.size() == k
){
res
.push_back(track
);
return;
}
for(int i
= start
; i
<= n
; ++i
){
track
.push_back(i
);
backTrack(track
, res
, n
, k
, i
+ 1);
track
.pop_back();
}
}
};
4.复杂度分析
时间复杂度 :
O
(
k
C
N
k
)
O(k C_N^k)
O(kCNk)，其中
C
N
k
=
N
!
(
N
−
k
)
!
k
!
C_N^k = \frac{N!}{(N - k)! k!}
CNk=(N−k)!k!N!是要构成的组合数。 空间复杂度 :
O
(
C
N
k
)
O(C_N^k)
O(CNk)
