216.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

# Author: Yu Zhou
# 216. Combination Sum III

# 比Combination Sum难度要Easy一些
# 思路就是注意剪枝

classSolution(object):
defcombinationSum3(self, size, target):
"""
 :type k: int
 :type n: int
 :rtype: List[List[int]]
 """
self.res= []

defdfs(size, remainder, temp, index):
iflen(temp) ==sizeandremainder==0:
self.res.append(temp[:])
#剪枝
iflen(temp) >size:
return
foriinxrange(index, 10):
temp.append(i)
dfs(size, remainder-i, temp, i+1)
temp.pop()
dfs(size, target, [], 1)
returnself.res