15-lines Python solution beat 95%


  • 0
    T

    x + (x+1) + .. + (x+k-1) = n
    => k(2x+k-1) / 2 = n
    => x = (2n+k-k^2) / 2k
    => x < (2n+k-k^2) // 2k+1

    def combinationSum3(self, k, n):
            if k <= 0 or n < 1: return []
            res = []
            def dfscom(kk, nn, ares):
                if 0 == kk: 
                    if nn == 0: res.append(ares)
                    return
                startn = ares[-1] + 1 if ares else 1
                div1, div2 = 2*nn+kk-kk*kk, 2*kk
                endn = min(11-kk, div1/div2 + 1)
                for i in range(startn, endn):
                    dfscom(kk-1, nn-i, ares + [i])
            dfscom(k, n, [])
            return res

Log in to reply
 

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