# 216. Combination Sum III 组合总和 III

@TOC

## # 题目描述：

Find all possible combinations of `k` numbers that add up to a number `n`, given that only numbers from `1 to 9` can be used and each combination should be a unique set of numbers.

Note:

1. All numbers will be positive integers.
2. The solution set must not contain duplicate combinations.

Example 1:

``````Input: k = 3, n = 7
Output: [[1,2,4]]
``````

Example 2:

``````Input: k = 3, n = 9
Output: [[1,2,6], [1,3,5], [2,3,4]]
``````

## # 解题方法

### # 方法一：DFS

``````class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
res = []
self.dfs(xrange(1, 10), k, n, 0, res, [])
return res

def dfs(self, nums, k, n, index, res, path):
if k < 0 or n < 0:
return
elif k == 0 and n == 0:
res.append(path)
return
for i in xrange(index, len(nums)):
self.dfs(nums, k - 1, n - nums[i], i + 1, res, path + [nums[i]])
``````

### # 方法二：回溯法

``````class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> res;
helper(res, {}, k, n, 0);
return res;
}
void helper(vector<vector<int>>& res, vector<int> path, int k, int n, int start) {
if (n < 0) return;
if (k == 0 && n == 0) res.push_back(path);
for (int i = start + 1; i <= 9; i ++) {
path.push_back(i);
helper(res, path, k - 1, n - i, i);
path.pop_back();
}
}
};
``````

## # 日期

2018 年 2 月 21 日 2018 年 12 月 20 日 —— 感冒害的我睡不着