class Solution(object):

def _combinationSum3Helper(self, remaining, candidates, next_value,

partial_sum, target):

"""

:type remaining: int. It's the count of additional numbers could be

used.

:type candidates: list[bool]. candidates[i] is True, if the number i is\

used.

:type next_value: int. It's the next number to consider.

:type partial_sum: int. The sum of used candidates so far.

:type target : int. It's the target sum.

:rtype: List[List[int]]

"""

result = []

if remaining == 0:

if partial_sum == target:

# Found one combination.

combination = []

for i in xrange(1, next_value):

if candidates[i] == True:

combination.append(i)

result.append(combination)

return result

else:

# This combination is not valid.

return result

elif partial_sum + next_value > target or next_value > 9:

# It's impossbile to have any valid combination with current

# prefix.

return result

else:

# It does not take the next_value.

result.extend(self._combinationSum3Helper(

remaining, candidates, next_value + 1, partial_sum, target))

# It does take the next_value.

candidates[next_value] = True

result.extend(self._combinationSum3Helper(

remaining - 1, candidates, next_value + 1,

partial_sum + next_value, target))

candidates[next_value] = False

return result

def combinationSum3(self, k, n):

"""

:type k: int

:type n: int

:rtype: List[List[int]]

"""

candidates = [False for _ in xrange(10)] # 0 is never used.

return self._combinationSum3Helper(k, candidates, 1, 0, n)