leetcode216 -- Combination Sum III

# 小郑之家~

### 题目


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:

All numbers will be positive integers.
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]]


### 解答


class Solution(object):
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
if k<=0 or n<=0:
return []

# temp = self.helper(range(1, n+1), n)
temp = self.helper(range(1,10), n)
res = []
for x in temp:
if len(x)==k:
res.append(x)

return res

def helper(self, candidates, target):
res = []

for i in range(len(candidates)):
if candidates[i]>target:
break
if candidates[i] == target:
res.append([candidates[i]])
break

temp = self.helper(candidates[i+1:], target-candidates[i])
for a in temp:
a.insert(0, candidates[i])
res.append(a)

return res