今日題目

題目連結：401. Binary Watch
題目主題：Backtracking, Bit Manipulation

簡單說說 Backtracking

Backtracking 有點像是 Enumeration 的進化，在 Enumeration 我們列出了所有可能的路出來，而 Backtracking 在列出所有可能性的過程已經發現不符合條件的路出現，就會往回走直接往新的路再去走。

找一個範例來說明，假設 nums = [5, 3, 2, 4, 1]，想要在這個 nums 中找出所有三個數加起來小於 8 的組合找出來，實際上 Backtracking 想像起來如下圖：

簡單來說，用 Enumeration 的方式先想像，但是在算的過程中，如果走到一半已經發現不可能符合條件了，就會直接往下一條路走了，這張圖紅色叉就代表這條路已經不用走下去了，紅色叉開始以下沒走到的都是提升效能的部份，最終可以找到[3, 2, 1] 及 [2, 4, 1] 這兩種可能。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

下圖是Leetcode的範例圖，可以看到這是一個 Binary Watch，這張圖的範例顯示的時間是 4:51。

這個 Binary Watch 分成上面的 4 個數字為小時範圍是是 0 - 11，下面的 6 個數字為分鐘範圍是 0 - 59，如果今天是 11:20 分，總共會亮 5 個燈，分別是小時的 8, 2, 1及分鐘的16 ,4 這五個燈。

題目會給你一個 turnedOn 為亮燈的數量，目的是要將所有可能性列出來，如果 turnedOn 給的是 5，就要把所有 5 個燈的可能性都列出來，最終回傳一個字串陣列。

另外要注意的是，小時若是個位數不用顯示前面的 0：
Ex. 不能顯示 "01:00"，應該顯示 "1:00"

若是分鐘的話，個位數需要顯示前面的 0：
Ex. 不能顯示 "10:2"，應該顯示"10:02"

約束：

• 0 <= turnedOn <= 10

範例1

輸入: turnedOn = 1
輸出: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
解說: 總共只有 10 個燈，因此就每個燈輪流亮一次即可得到這個答案。

範例2

輸入: turnedOn = 9
輸出: []
解說: 總共有 10 個燈，但不可能 9 個燈同時亮，舉例來說若小時的四個燈全亮，數字總共已經到了 15 已經超過範圍 0 - 11 了，因此在這個範例最後回傳的是空陣列。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 宣告 hours 及 minutes 紀錄所有會亮的數字。
2. 寫兩個遞迴方法，分別為取得小時數及分鐘數。
3. 取得小時遞迴方法：
   • 若有符合條件的小時出現，呼叫取得分鐘的遞迴方法。
   • 若出現大於 11 以上的小時數，繼續往下個可能性確認。
   • 若超過指定亮燈數，繼續往下個可能性確認。
   • 跑一個迴圈，用一個 Stack 來紀錄，目前亮燈的小時數組合。
   • 最終回傳目前符合條件的字串列表。
4. 取得分鐘遞迴方法：
   • 若有符合條件的分鐘出現，將目前小時數及分鐘數組合成字串，放進字串列表。
   • 若出現大於 59 以上的分鐘數，繼續往下個可能性確認。
   • 若超過指定亮燈數，繼續往下個可能性確認。
   • 跑一個迴圈，用一個 Stack 來紀錄，目前亮燈的分鐘數組合。
   • 最終回傳目前符合條件的字串列表。
5. 若指定亮燈數是 0 回傳 ['0:00'] 一種可能，若指定亮燈樹有1以上，從取得小時數的遞迴方法開始走。

圖解過程

範例：turnedOn = 8

這次用的範例目標是要亮 8 個燈，下圖是列出的是運作的過程：

上圖中可以看到，實際運作過程會先從 hours 開始檢查，其中 hours 只有亮 1 個燈及 2 個燈的狀況有個箭頭指到一個 X 是因為，如果小時只有亮 1 或 2 個燈，要符合 8 個燈的條件，代表 minutes 需要亮到 7 或 6 個燈，但實際上分鐘的燈也只有 6 個， 6 個都亮會超過分鐘最大值59了，因此直接在這邊結束，沒有去查到分鐘。

另外比較特別的是 [8, 4] 這個組合，沒有箭頭直接看到 X 的原因是，8 + 4 已經等於 12 了，已經超過最大小時數，因此在這邊直接結束不用繼續往下去查看。

最後是 [8, 2, 1] 及 [4, 2, 1] 這兩組小時數，都是亮 3 個燈，代表分鐘要亮 5 個燈，兩組小時都會找到同樣的分鐘組合，最後列出的結果是 ["11:59", "11:55", "11:47", "11:31", "7:59", "7:55", "7:47", "7:31"]。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    # 先準備好小時及分鐘的所有燈
    def __init__(self):
        self.hours = [8, 4, 2, 1]
        self.minutes = [32, 16, 8, 4, 2, 1]
        
    # 取得可能的小時數
    def getHours(self, timeList, turnedOn, startIndex, hourStack = []):
        # 若超過 11 小時以上結束
        if sum(hourStack) >= 12: return timeList
        # 若亮燈樹符合條件，取得目前小時數的所有分鐘數，並且放進最終要回傳的字串列表中
        if len(hourStack) <= turnedOn:
            timeList = self.getMins(timeList, sum(hourStack), turnedOn-len(hourStack), 0)
        # 若已經等於指定亮燈數結束
        if len(hourStack) == turnedOn: return timeList
        # 繼續組合可能的小時數
        for hourIndex in range(startIndex, len(self.hours)):
            hourStack.append(self.hours[hourIndex])
            timeList = self.getHours(timeList, turnedOn, hourIndex+1, hourStack)
            hourStack.pop()
        return timeList
            
    # 取得可能的分鐘數
    def getMins(self, timeList, hour, turnedOn, startIndex, minStack = []):
        # 若亮燈數超過分鐘總燈數結束
        if turnedOn >= len(self.minutes): return timeList
        # 若超過 59 分鐘以上結束
        if sum(minStack) >= 60: return timeList
        # 若亮燈數符合條件，取得目前小時數的所有分鐘數
        if len(minStack) == turnedOn:
            minute = sum(minStack)
            minStr = f"0{minute}" if minute < 10 else minute
            timeList.append(f"{hour}:{minStr}")
            return timeList
        # 繼續組合可能的分鐘數
        for minIndex in range(startIndex, len(self.minutes)):
            minStack.append(self.minutes[minIndex])
            timeList = self.getMins(timeList, hour, turnedOn, minIndex+1, minStack)
            minStack.pop()
        return timeList
    
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        # 若沒有任何燈亮直接回傳 0:00 一種可能，若有亮燈開始走遞迴方法
        return ['0:00'] if turnedOn == 0 else self.getHours([], turnedOn, 0)

希望您今天能瞭解到...

1. Backtracking 的基本概念
2. 401. Binary Watch 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：1863. Sum of All Subset XOR Totals