对回溯感到困惑吗？

Question

我试图解决这个问题Leetcode Question，但是我得到了一个错误，我超过了时间限制。你知道吗

class Solution:  

def readBinaryWatchHelper(self,hours, minutes, num, pastHours, pastMinutes):
    if num == 0:
        hour, minute = sum(pastHours), sum(pastMinutes)
        if self.isValidTime(hour, minute):
            time = str(hour) + ":" + str(minute).zfill(2)
            self.times.add(time)
    else:
        for i in minutes:
            cMinutesTemp = list(minutes)
            pMinutesTemp = list(pastMinutes)
            pMinutesTemp.append(i)
            cMinutesTemp.remove(i)
            if self.isValidTime(sum(pastHours), sum(pMinutesTemp)):
                self.readBinaryWatchHelper(hours, cMinutesTemp, num - 1, pastHours, pMinutesTemp)    
        for i in hours:
            cHoursTemp = list(hours)
            pHoursTemp = list(pastHours)
            pHoursTemp.append(i)
            cHoursTemp.remove(i)
            if self.isValidTime(sum(pHoursTemp), sum(pastMinutes)):
                self.readBinaryWatchHelper(cHoursTemp, minutes, num - 1, pHoursTemp, pastMinutes)


@staticmethod
def isValidTime(hours, minutes):
    if hours < 12 and minutes < 60:
        return True
    return False

def readBinaryWatch(self, num):
    self.times = set()
    hChoices = [1,2,4,8]
    mChoices = [1,2,4,8,16,32]
    self.readBinaryWatchHelper(hChoices[::-1], mChoices[::-1], num, [],[])
    return list(self.times)

这就是我用回溯法写的解决方案。我希望我能得到反馈为什么它太慢了？其中一个有效的解决方案就是把从0到12的小时数和从0到60的分钟数的所有组合取出来，然后检查这些位的和，看它们加起来是否正确。我搞不懂这个解决方案怎么比我的快？我的不应该因为“修剪树木”而更快吗？谢谢你们。你知道吗

Answer 1

不带回溯但使用itertools和list comp的解决方案是：

class Solution:
    def readBinaryWatch(self, num):
        """
        :type num: int
        :rtype: List[str]
        """
        from itertools import combinations,  product
        hhmin = min(num,3)+1 # only generate at much as needed
        mmmin = min(num,5)+1 # only generate as much as needed
        nBits = [1,2,4,8,16,32]

        # {0: ['0'], 1: ['1','2','4','8'], 2: ['3','5','9','6','10'], 3: ['7','11']} for>2 
        h = { bitCount: list(str(sum(x)) for x in combinations(nBits,bitCount) 
                          if sum(x) < 12) for bitCount in range(hhmin)}

        m = { bitCount: list(str(sum(x)).zfill(2) for x in combinations(nBits,bitCount) 
                          if sum(x) < 60) for bitCount in range(mmmin)}

        ranges = ((h[subl[0]],m[subl[1]]) for subl in (x for x in product(range(num + 1),
                          range(num + 1)) if sum(x) == num and x[0]<hhmin and x[1]<mmmin))

        return ["{0}:{1}".format(hh,mm) for (hhhh,mmmm) in ranges 
                                        for hh in hhhh for mm in mmmm]

测试方法：

s = Solution()
for n in range(8):
    print(s.readBinaryWatch(n))
    print() 

它拨入55ms到64ms之间，这取决于不同提交之间的任何内容。根据页面显示，这一数字达到了77%——有一些更简短、更优美的解决方案。你可以检查其中一些一旦你提交一个。不幸的是，你的根本没有运行，递归需要递归，这似乎太慢了。你知道吗

有趣的是，预制床列表中的“暴力力量”低于50%——只需尝试一下；）