<div>
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].
You may return the answer in any order.
Example 1:
<pre>Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] </pre>
Example 2:
<pre>Input: n = 1, k = 1 Output: [[1]] </pre>
Constraints:
1 <= n <= 201 <= k <= n
</div>
题目大意：
求大小为k的所有可能组合
解题思路：
用组合模板，先排序
解题步骤：
N/A
注意事项：
- 引入k作为模板API中的target，k为0作为终止条件。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# char dfs (type 2 linear) Leetcode 77 Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]
def combine(self, n: int, k: int) -> List[List[int]]:
nums = [i + 1 for i in range(n)]
path, res = [], []
self.dfs2(nums, 0, k, [], res)
return res
def dfs2(self, nums, start, k, path, res):
if len(path) == k:
res.append(list(path))
return
for i in range(start, len(nums)):
path.append(nums[i])
self.dfs2(nums, i + 1, k, path, res)
path.pop()
算法分析：
时间复杂度为<code>O(kC<sup>k</sup><sub>n</sub>)</code>，解大小乘以path长度, 空间复杂度O(n)
