Python backtracking (since it is also tagged "Backtracking")


  • 0
    A
    def getSumsDFS(self, count, bases, basesIndex, sum, sums, isHour):
        if count == 0:
            if isHour and sum <= 11 or not isHour and sum <= 59:
                sums.append(sum)
        else:
            for i in range(basesIndex, len(bases)):
                self.getSumsDFS(count - 1, bases, i + 1, sum + bases[i], sums, isHour)
    
    def getSums(self, setBits, bases, isHour):
        sums = []
        self.getSumsDFS(setBits, bases, 0, 0, sums, isHour)
        return sums
    
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        hourBases = [8, 4, 2, 1]
        minuteBases = [32, 16, 8, 4, 2, 1]
        
        getSums = self.getSums
        result = []
        
        for hourSetBits in range(num + 1):
            if hourSetBits <= len(hourBases) and num - hourSetBits <= len(minuteBases):
                hours = getSums(hourSetBits, hourBases, True)
                minutes = getSums(num - hourSetBits, minuteBases, False)
                for h in hours:
                    for m in minutes:
                        result.append("%d:%02d" % (h, m))
        return result

Log in to reply
 

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