Python solution with Combinations


  • 0
    L

    Pascal triangle's elem can represent by combinations: (e.g. (4, 2) = C(4, 2) = 6)

                        (0, 0)
    
                   (1, 0)  (1, 1)
    
             (2, 0)  (2, 1)  (2, 2)
    
         (3, 0)  (3, 1)  (3, 2)  (3, 3)
    
    (4, 0)  (4, 1)  (4, 2)  (4, 3)  (4, 4)
    

    Code:

    class Solution:
    # @return a list of lists of integers
    def generate(self, numRows):
        
        def bin_coefficient(n, k):
            # @return c(n, k)
            if k == 0:
                return 1
            return reduce(operator.mul, xrange(n-k+1, n+1)) / reduce(operator.mul, xrange(1, k+1))
        
        pascal_triangle = [[bin_coefficient(n, k) for k in xrange(n+1)] for n in xrange(numRows)]
        return pascal_triangle

  • 0
    M

    can you explain how this solution works ?


  • 0
    L

    Which part do you fell hard to understand?


  • 0
    M

    this particular line : return reduce(operator.mul, xrange(n-k+1, n+1)) / reduce(operator.mul, xrange(1, k+1))


  • 0
    L

    In combinations, C(n, k) = (n * (n-1) * ... * (n-k+1)) / (k * (k-1) * ... * 1).
    This line is to calculate C(n, k)


Log in to reply
 

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