Python backtracking


  • 0
    class Solution(object):
        def readBinaryWatch(self, num):
            """
            :type num: int
            :rtype: List[str]
            """
            temp = []
            r = []
            self.helper(num, temp, r, 0, -1)
            return r
            
        def helper(self, num, temp, r, index, last):
            if index == num:
                h = 0
                m = 0
                for i in temp:
                    if i > 3:
                        m += pow(2, i - 4)
                    else:
                        h += pow(2, i)
                if h < 12 and m < 60:
                    r.append("{}:{:0>2}".format(h, m))
            else:
                for i in range(last + 1, 10):
                    if index >= len(temp):
                        temp.append(i)
                    else:
                        temp[index] = i
                    self.helper(num, temp, r, index + 1, i)

  • 0
    N

    @逼里有蛇 I implemented this in Python as well. However, I can only pass some test cases. Could you please let me know what went wrong in my code? thanks!!

    class Solution(object):
        def readBinaryWatch(self, num):
            """
            :type num: int
            :rtype: List[str]
            """
            hours = [1, 2, 4, 8]
            minutes = [1, 2, 4, 8, 16, 32]
            self.res=[]
            self.helper(num, hours, minutes, 0, 0, 0, 0)
            return self.res
            
            
        def helper(self, num, hours, minutes, h, m, pos1, pos2):
            if num==0:
                if m>9:
                    self.res.append(str(h)+':'+str(m))
                    return
                else:
                    self.res.append(str(h)+':0'+str(m))
                    return
                    
            for i in range(pos1, len(hours)):
                if h+hours[i]<=11:
                    h+=hours[i]
                    self.helper(num-1, hours, minutes, h, m, i+1, pos2)
                    h-=hours[i]
    
            
            for j in range(pos2, len(minutes)):
                if m+minutes[j]<=59:
                    m+=minutes[j]
                    self.helper(num-1, hours, minutes, h, m, pos1, j+1)
                    m-=minutes[j]
    
    

  • 0
    This post is deleted!

  • 0

    @niufen There are duplicated outputs in your codes because you use 2 loops in your helper. The combinations appear in the first loop will appear again on the second loop.


Log in to reply
 

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