# Clean 1/6/7-liners (AC)

• Batteries Included
AC in 44ms

First the obligatory "use the darn library" solution. Create all k-combinations of digits and keep those with sum n:

``````from itertools import combinations

class Solution:
def combinationSum3(self, k, n):
return [c for c in combinations(range(1, 10), k) if sum(c) == n]
``````

Recursive
AC in 48 ms

But it's more interesting to do it on your own. Here I use a recursive helper function getting the same k and n as the main function, and an additional cap under which all the numbers have to be:

``````class Solution:
def combinationSum3(self, k, n):
def combs(k, n, cap):
if not k:
return [[]] * (not n)
return [comb + [last]
for last in range(1, cap)
for comb in combs(k-1, n-last, last)]
return combs(k, n, 10)
``````

Iterative
AC in 56 ms

And an iterative version doing pretty much the same thing, except this time I prepend elements on the left, and use the first element of a partial combination as the cap.

``````class Solution:
def combinationSum3(self, k, n):
combs = [[]]
for _ in range(k):
combs = [[first] + comb
for comb in combs
for first in range(1, comb[0] if comb else 10)]
return [c for c in combs if sum(c) == n]
``````

Reduce
AC in 44 ms

And here's a "one-liner" version of the iterative solution using `reduce` instead of the loop:

``````class Solution:
def combinationSum3(self, k, n):
return [c for c in
reduce(lambda combs, _: [[first] + comb
for comb in combs
for first in range(1, comb[0] if comb else 10)],
range(k), [[]])
if sum(c) == n]
``````

I note that all these solutions also correctly solve the cases with k=0 and/or n=0 (but leetcode sadly doesn't test those).

• The k = 0 and n = 0 test cases were not included on purpose. The available set of numbers for filling the array is of the range 1 to 9. A sum of n = 0 would not be possible with a minimum of 1. And there is no possibility of filling in numbers if array size is k = 0.

Moreover, always having a test case (null or invalid) to break the submitter's code seems a bit too much these days. :)

• There's nothing "null" or "invalid" about those cases. If both k=0 and n=0, then there is exactly one combination, namely the empty combination. It has zero numbers and they add up to zero. So the answer is simply `[[]]`. In all other cases where k=0 or n=0 or even k<0 or n<0, there is no combination, so the answer is `[]`.

Also, solutions often get simpler the more basic your base cases are. Here's a good example of someone having unnecessarily complicated code possibly because he didn't (have to) think of more basic base cases. It's a missed opportunity.

• Alright, rephrasing it to "'null' or 'invalid' or 'not possible' in the context of the application of the problem"

The application of the problem (for solving a puzzle) did not require the k = 0 and n = 0 case because that case simply does not exist for the puzzle. I did not include k = 0 and n = 0 test case in the OJ on purpose, while setting the problem.

I agree with you on the fact the solution gets simple if you start looking at things from the base case.

PS: The puzzle is like Sudoku: 1 to 9 without 0's

• Similar to the second solution and slightly faster (not sure why, ~35ms)

``````class Solution(object):
def combinationSum3(self, k, n, pres = [[1], [2], [3], [4], [5], [6], [7], [8], [9]]):
if k == 1:
return [pre for pre in pres if sum(pre) == n]
return self.combinationSum3(k-1, n, [pre+[d] for pre in pres
for d in range(pre[-1], 10)
if d not in pre and sum(pre)+d<=n])
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.