題目

解題概念

  • 此題簡單來說就是要用火柴去拚一個正方形，且不能用折火柴的方式
  • 此題為所謂 Backtracking(回朔法) 的題型
    • Def :
      • 利用 Recursion 依序窮舉各個層次的 Value，並製作所有可能的 Value 組合
      • 而在 Recursion 中，需避免創造出不正確的 Value 組合
    • 類似題型 : Enumerate Permutations、Enumerate Combinations、8 Queen Problem、0/1 Knapsack Problem…
    • 詳細解釋 : https://web.ntnu.edu.tw/~algo/Backtracking.html
  • 而以下是幾個較為重要的解題概念 :
    1. 確認所有火柴能不能拚成正方形
      • 加總所有的火柴長度，確認其是否為4的倍數
      • 也就是判斷能不能畫出正方形所需4個等長的邊
      • 若不行，則直接回傳 False 即可
    2. 將4個等長的邊，當作是4個 Bucket
      • 我們要做的，就是從 matchsticks 陣列中，各別取出單一火柴並確認是否能放入這4個Bucket，且要放入哪個 Bucket
    3. 在各別取出火柴時，會從最長的火柴開始挑，這樣可以快速地確認是否能放得下所有 Bucket
    4. 最後取出火柴並嘗試放入 Bucket 時，會使用上述提到之 Backtracking 法

實際寫Code

  • 目標函式 : makesquare(matchsticks)
    • Input : matchsticks : List[int]
    • Output : bool
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # 解題概念 1
    s = sum(matchsticks)
    if(s == 0 or s % 4 != 0):
        return False
    target = s / 4 # target為目標邊長

    # 解題概念 2
    bucket = [0,0,0,0] # 代表4個邊

    # 解題概念 3
    # 透過sort()，將matchsticks陣列反向排序，讓數值從大到小排列
    matchsticks.sort(reverse=True)

    L = len(matchsticks)

    # 解題概念 4
    # def find(...): ...

    return find(0) # 從index = 0開始找
  • 主要遞迴 : ( 運用Python的函數中可以放函數的特性 ) 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    def  find(index): # 確認在 matchsticks[index] 放入任一 Bucket 是否可行

        # 遞迴終止條件 : 當 index == 元素數時，確認 4 個 Bucket 的數值是否相等
            # 若相等 : 可組合一正方形
            # 若不相等 : 不可組合正方形
        if index == L:
                return (bucket[0] == bucket[1]) and (bucket[1] == bucket[2]) and (bucket[2]==bucket[3])

        # 依序針對 4 個 Bucket
        for i in range(0, 4):

            value = matchsticks[index] # 此回合欲放入 Bucket 之數值

            if bucket[i] + matchsticks[index] <= target : # 若 value 可放入此 Bucket

                bucket[i] += matchsticks[index] # 假裝此 Bucket 已放入 Value

                if find(index+1): # 運用遞迴，確認尚未分配之元素是否能順利置入 Bucket
                    return True # 若可以，回傳 True

                bucket[i] -= matchsticks[index] # 恢復此 Bucket 的值

            # 若無法放入，則回傳 False
            return False

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def makesquare(self, matchsticks):
    """
    :type matchsticks: List[int]
    :rtype: bool
    """
    L = len(matchsticks)

    # 解題概念 1
    s = sum(matchsticks)
    if(s == 0 or s % 4 != 0):
        return False
    target = s / 4 # target為目標邊長

    # 解題概念 2
    bucket = [0,0,0,0]    

    # 解題概念 3
    matchsticks.sort(reverse=True)

    # 解題概念 4
    def  find(index):

        if index == L:
            return (bucket[0] == bucket[1]) and (bucket[1] == bucket[2]) and (bucket[2]==bucket[3])

        for i in range(0, 4):
            value = matchsticks[index]
            if bucket[i] + value <= target:
                bucket[i] += value
                if find(index+1):
                    return True
                bucket[i] -= value
            return False
        
        return find(0)

參考資料

  1. 台師大 Backtracking 線上教材