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]
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)
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 if comb else 10)] return [c for c in combs if sum(c) == n]
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 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 = [, , , , , , , , ]): 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.