Python combinatorics + caching, beats 95%


  • 0
    Y
    def subsets_n_k(n, k, cache=None):
        # https://leetcode.com/problems/combinations/description/
        if cache is None:
            cache = {}
        cache_key = (n, k)
        if cache_key in cache:
            pass
        elif n == k:
            cache[cache_key] = [range(1, n+1)]
        elif k == 1:
            cache[cache_key] = [[j] for j in xrange(1, n+1)]
        else:
            excl = subsets_n_k(n-1, k, cache)
            incl = [
                subset + [n]
                for subset in subsets_n_k(n-1, k-1, cache)
            ]
            cache[cache_key] = excl + incl
        return cache[cache_key]
    
    

Log in to reply
 

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