# 77. Combinations 组合

@TOC

## # 题目描述

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

``````For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
``````

## # 解题方法

### # 方法一：递归

``````class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []
self.helper(range(1, n + 1), k, res, [])
return res

def helper(self, array, k, res, path):
if k > len(array):
return
if k == 0:
res.append(path)
else:
self.helper(array[1:], k - 1, res, path + [array[0]])
self.helper(array[1:], k, res, path)
``````

### # 方法二：回溯法

``````class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
res = []
self.helper(range(1, n + 1), k, res, [])
return res

def helper(self, array, k, res, path):
if k > len(array):
return
if k == 0:
res.append(path)
else:
for i in range(len(array)):
self.helper(array[i + 1:], k - 1, res, path + [array[i]])
``````

C++代码如下：

``````class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<int> nums(n, 0);
for (int i = 1; i <= n; i++) {
nums[i - 1] = i;
}
vector<vector<int>> res;
helper(nums, res, {}, 0, k);
return res;
}
void helper(const vector<int>& nums, vector<vector<int>>& res, vector<int> path, int start, int remain) {
if (start > nums.size()) return;
if (remain == 0) {
res.push_back(path);
return;
}
for (int i = start; i < nums.size(); i++) {
path.push_back(nums[i]);
helper(nums, res, path, i + 1, remain - 1);
path.pop_back();
}
}
};
``````

## # 日期

2018 年 3 月 11 日 2018 年 12 月 20 日 —— 感冒害的我睡不着