# Beating 95% Python solution using recursion with comments

• Actually combination Sum I,II, III are very similar. We only need to modify our solution a little bit to meet the requirements. My solution for Sum II is here.

``````def combinationSum3(self, k, n):
# We don't need to sort, because each number only can be used once,
# and all they are all positive.
result = []
self.combination_sum_3(k, 1, n, [], result)
return result

def combination_sum_3(self, length, start, target, path, result):
# In this problem, I give a property `length` to track the current length of
# our path. We decrease the length by 1 each recursive call. So in the base
# case here we only need to check whether the length is 0 (the real length
# of path is exactly 3).
# The design of `target` is still the same as Sum I and II.
if not target and not length:
result.append(path)
return

for i in xrange(start, 10):
# Avoid unnecessary searching, since all the numbers are positive.
if not length or i > target:
return

# We set `start` as `i + 1` because all candidates only could be
# used once, otherwise we set it as `i`.
self.combination_sum_3(length - 1, i + 1, target - i, path + [i], result)
``````