Question: https://leetcode.com/problems/combination-sum-iii/

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | 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) |

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 [[100]] 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!

Hi Sheng,

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.

My 2cents!

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:

Just,