Solution to Combination Sum III by LeetCode

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.

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)

Here’s my solution. The feature is that it doesn’t make failed iterations.

class Solution(object):

def __init__(self):

self.start = 1

self.end = 9

def combinationSum3Step(self, subset, sum):

if len(subset) == self.k:

self.list.append(subset)

return

# number of remaining subset items after adding one more

remLen = self.k - len(subset) - 1

# last subset item

lastItem = subset[-1] if len(subset) else 0

# each item should be greater than his left neighbor, so:

# 1. next item should be greater or equal to {lastItem + 1},

# but anyway last item of fulfilled subset should be {n - sum}

item = lastItem + 1 if remLen else self.n - sum

# 2. next item should be less or equal to [n - sum - min_sum_of_rest],

# where min_sum_of_rest is arithmetic progression:

# step = 1, start = item + 1, number_of_items = remLen

while item <= self.end and item <= self.n - sum - (2 * item + remLen + 1) * remLen / 2:

# each item should be greater or equal to [n - sum - max_sum_of_rest],

# where max_sum_of_rest is arithmetic progression:

# step = 1, end = self.end, number_of_items = remLen

if item >= self.n - sum - (2 * self.end - remLen + 1) * remLen / 2:

self.combinationSum3Step(subset + [item], sum + item)

item += 1

def combinationSum3(self, k, n):

"""

:type k: int

:type n: int

:rtype: List[List[int]]

"""

if k < 1 or n < 1:

raise Exception('invalid args')

self.list = []

self.k = k

self.n = n

self.combinationSum3Step([], self.start - 1)

return self.list

Solution to Combination Sum III by LeetCode

7 Replies to “Solution to Combination Sum III by LeetCode”

Leave a Reply Cancel reply