Python Recursive Solution with explanation


  • 0

    I believe this code could be more concise.

    Separate the number of lights (input) into two parts: hours and minutes.
    Each part can be regarded as combination of number light, and can be easily obtained by recursion.

    For example, if total input is 3, if (hr : min) = (3 : 0) => pick combination of 3 from [1,2,4,8]

    Note that we need to set limit to eliminate those invalid reads, such as 13:xx, yy:62.

    class Solution(object):
        def readBinaryWatch(self, num):
            if num > 8: return []        # no such possibility
    
            res, hrbase, minbase = [], [1,2,4,8], [1,2,4,8,16,32]
    
            for i in xrange(4):        # length of hrbase
                numofhr, numofmin, hrs, mins = i, num-i, [], []
                self.getNum(numofhr, 11, hrbase, hrs)
                self.getNum(numofmin, 59, minbase, mins)
    
                for h in hrs:
                    for m in mins:
                        time = "{}:".format(h)+str(m).zfill(2)
                        res.append(time)
    
            return res
    
        def getNum(self, n, limit, base, reads, pathsum=0):
            if len(base) < n or pathsum > limit:      # invalid reads, e.g. 12:xx, xx:60
                return
            if n == 0 and pathsum == 0:
                reads.append(0)
                return
            elif len(base) == n and pathsum+sum(base) <= limit:
                reads.append(pathsum+sum(base))
                return
            if n == 0:
                reads.append(pathsum)      # base case
                return
            for i in xrange(len(base)):        # recursion case
                self.getNum(n-1, limit, base[i+1:], reads, pathsum+base[i])
    

Log in to reply
 

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