Question Name: Combination Sum III
This is a typical recursion problem. Find out the base case and recursive cases, and that’s the right solution.
Solution to Combination Sum III by LeetCode
def _combinationSum3Helper(self, remaining, candidates, next_value,
:type remaining: int. It's the count of additional numbers could be
:type candidates: list[bool]. candidates[i] is True, if the number i is\
: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.
result = 
if remaining == 0:
if partial_sum == target:
# Found one combination.
combination = 
for i in xrange(1, next_value):
if candidates[i] == True:
# This combination is not valid.
elif partial_sum + next_value > target or next_value > 9:
# It's impossbile to have any valid combination with current
# It does not take the next_value.
remaining, candidates, next_value + 1, partial_sum, target))
# It does take the next_value.
candidates[next_value] = True
remaining - 1, candidates, next_value + 1,
partial_sum + next_value, target))
candidates[next_value] = False
def combinationSum3(self, k, n):
:type k: int
:type n: int
candidates = [False for _ in xrange(10)] # 0 is never used.
return self._combinationSum3Helper(k, candidates, 1, 0, n)
IMHO, that sounds too much. If we restrict the elements in the array in an increasing order, there is no need to track if a number in range [1, 9] has been used.
There is actually a bug in Leetcode testing code: given “1,100”, leetcode considers [] as a valid answer, which breaks the rule that only number from [1, 9] can be considered for the combination…
Yes, you are right. Also because the result always has the fix length k. Thanks!
You are kind. I was not completely right. Your code is fine. I should have read it thoroughly. list[bool] is not for tracking, it’s for storing. It saves the possible combination. That has been said, the extra recursion branch (with or without next_value, sounds like a DP approach) may not be necessary.
Actually, my original plan is using the linked list in array candidate. I gave up because I am too lazy 🙂
Here’s my solution. The feature is that it doesn’t make failed iterations.
Actually, the condition below is not necessary: