Clean 1/6/7-liners (AC)

  • 10

    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]

    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[0] 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[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).

  • 0

    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. :)

  • 0

    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.

  • 0

    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

  • 0

    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])

Log in to reply

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