回溯法III：生成所有長度為 n 的二進制數組

 生成所有長度為 n 的二進制數組，並展示了回溯法的基本概念。以下是詳細解釋：

程式碼逐步解釋

1. generate_binary(n, path) 函式：

   def generate_binary(n, path):
       if n == 0:
           print(''.join(path))
           return
       
       generate_binary(n - 1, path + ['0'])
       generate_binary(n - 1, path + ['1'])
   

   • 目標： 生成長度為 n 的所有二進制數組。
   • 遞迴終止條件： 當 n == 0 時，表示已經生成了一個完整的二進制數組，把 path 中的內容印出來，並返回結束該遞迴分支。
   • 遞迴：
     • 使用 generate_binary(n - 1, path + ['0']) 嘗試在當前組合加入 '0'，並遞迴生成下一層。
     • 使用 generate_binary(n - 1, path + ['1']) 嘗試在當前組合加入 '1'，並遞迴生成下一層。
   • 這兩個遞迴分支會生成所有可能的二進制組合。

2. 主程式的 for 迴圈：

   for i in range(1, 5):
       generate_binary(i, [])
       print()
   

   • 目標： 測試不同長度的二進制組合生成。
   • 使用 for 迴圈來調用 generate_binary 函式，當 i = 1 時生成長度為 1 的二進制組合，當 i = 2 時生成長度為 2 的二進制組合，依此類推直到 i = 4。
   • 每生成完一組長度的二進制組合後，印出一個空行來分隔不同組合的結果。

輸出結果解釋

1. 當 n = 1：

   0
   1
   

   • 生成了所有長度為 1 的二進制數組。

2. 當 n = 2：

   00
   01
   10
   11
   

   • 生成了所有長度為 2 的二進制數組。

3. 當 n = 3：

   000
   001
   010
   011
   100
   101
   110
   111
   

   • 生成了所有長度為 3 的二進制數組。

4. 當 n = 4：

   0000
   0001
   0010
   0011
   0100
   0101
   0110
   0111
   1000
   1001
   1010
   1011
   1100
   1101
   1110
   1111
   

   • 生成了所有長度為 4 的二進制數組。

程式運作流程：

1. 每次遞迴都會將 n 減 1，並且把當前的 '0' 或 '1' 加到 path 中。
2. 當 n 減到 0 時，就將目前累積的 path 印出來。
3. 程式會自動回到上一層，繼續探索其他未嘗試的選擇，這就是回溯的概念。

總結

• 回溯法： 程式遞迴地嘗試加入 '0' 和 '1'，當達到指定長度時印出結果，然後回到上一層繼續嘗試其他可能性。
• 用途： 這種方法非常適合生成所有排列組合或遍歷樹狀結構的問題。