Iterative 8-line solution using C(n, k) = C(n-1, k) + C(n-1, k-1)


  • 1
    T

    Raw solution:

    def combine(self, NN, K):
            result = [[[]]]
            for n in range(1, NN+1):
                newRes = [[[]]]  #C(n, 0) = 0
                for k in range(1, n):
                    #C(n, k) = C(n-1, k) + C(n-1, k-1)
                    newRes.append(result[k] + [_ + [n] for _ in result[k-1]]) 
                #C(n, n) = C(n-1, n-1) = 1
                newRes.append([result[n-1][0] + [n]]) 
                result = newRes
            return result[K]
    

    After speed up:

    def combine(self, NN, K):
            result = [[[]]]
            for n in range(1, NN+1):
                newRes = [[[]]]  #C(n, 0) = 0
                #speed up, ignore C(n, K+1),  C(n, K+2), C(n, K+3)...
                for k in range(1, min(K+1, n)):
                    #C(n, k) = C(n-1, k) + C(n-1, k-1)
                    newRes.append(result[k] + [_ + [n] for _ in result[k-1]]) 
                if n < K + 1: 
                    newRes.append([result[n-1][0] + [n]]) #C(n, n) = C(n-1, n-1) = 1
                result = newRes
            return result[K]
    

    After space compression:

    def combine(self, NN, K):
            result = [[[]]]
            for n in range(1, NN+1):
                lastRes = result[0]
                for k in range(1, n):
                    #C(n, k) = C(n-1, k) + C(n-1, k-1)
                    lastRes, result[k] = result[k], result[k] + [_ + [n] for _ in lastRes]
                #C(n, n) = C(n-1, n-1) = 1
                result.append([lastRes[0] + [n]]) 
            return result[K]

Log in to reply
 

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