# 探索 Backtracking：從巢狀迴圈到遞迴解法

在程式設計中，解決組合問題時常常需要遍歷所有可能的組合。然而，隨著問題規模的擴大，使用簡單的巢狀迴圈可能會導致程式碼冗長且效率低下。這時，Backtracking（回溯法）提供了一種更為優雅且高效的解決方案。本文將帶你從巢狀迴圈的基礎開始，逐步引入 Backtracking 的概念，並展示如何將其應用於實際的 C++ 程式碼中。

## 簡單的巢狀迴圈

首先，我們來看看使用巢狀迴圈解決排列組合問題的基本方法。以下是一個生成所有不重複的三位數排列的例子：

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            for (int k = 1; k <= 3; k++) {
                if (i == j || i == k || j == k) continue;
                cout << i << " " << j << " " << k << endl;
            }
        }
    }
    return 0;
}

這段程式碼通過三層巢狀迴圈遍歷所有可能的組合，並在內部加入條件判斷以避免重複。然而，這種方法存在一個問題：當 `i == j` 或其他條件成立時，判斷是在最後一層迴圈才進行的，這意味著即使前兩層的組合已經無效，第三層仍然會被執行，導致不必要的計算。

## 提早判斷：Backtracking 的精神

為了解決上述問題，我們可以在更早的層級進行條件判斷，從而避免不必要的迴圈執行。這正是 Backtracking 的核心思想，即在可能的時候提前剪枝，減少計算量。以下是改進後的程式碼：

#include <iostream>
using namespace std;

int main() {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            if (i == j) continue;
            for (int k = 1; k <= 3; k++) {
                if (j == k) continue;
                cout << i << " " << j << " " << k << endl;
            }
        }
    }
    return 0;
}

在這個版本中，我們在第二層迴圈中檢查 `i == j`，如果成立則跳過第三層迴圈的執行。同樣地，在第三層迴圈中檢查 `j == k`。這樣一來，無效的組合將被及早排除，提升了程式的效率。

然而，這種方法並不通用。當我們需要處理更深層次的巢狀迴圈時，手動添加判斷條件會變得繁瑣且難以維護。因此，我們需要一種更通用的方法來處理任意深度的迴圈結構。

## 通用的 Backtracking 解法

為了實現通用的 Backtracking 解法，我們可以將巢狀迴圈轉換為遞迴（遞迴）函式。這不僅使程式碼更加簡潔，也便於處理任意深度的組合問題。以下是具體的實現步驟：

### A. 改變重複子結構

首先，我們將巢狀迴圈中的變數轉換為一個陣列，這樣可以通過遞迴來遍歷每一層的可能值。以下是將巢狀迴圈改寫為使用陣列的版本：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> path(3);
    
    for (path[0] = 1; path[0] <= 3; path[0]++) {
        for (path[1] = 1; path[1] <= 3; path[1]++) {
            for (path[2] = 1; path[2] <= 3; path[2]++) {
                cout << path[0] << " " << path[1] << " " << path[2] << endl;
            }
        }
    }
    
    return 0;
}

這段程式碼使用一個 `vector<int>` 來存儲每一層的值，並透過迴圈來填充陣列。雖然這樣做已經比多層巢狀迴圈更具彈性，但仍然限制於固定的層數。

### B. 使用遞迴函式

為了進一步提升程式碼的通用性，我們將巢狀迴圈轉換為遞迴函式，讓每一層的處理都由函式呼叫自身來完成。這樣可以輕鬆處理任意深度的組合問題。以下是改寫後的程式碼：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void f(int level, vector<int>& path) {
    if (level == 3) {
        cout << path[0] << " " << path[1] << " " << path[2] << endl;
        return;
    }

    for (path[level] = 1; path[level] <= 3; path[level]++) {
        f(level + 1, path);
    }
}

int main() {
    vector<int> path(3);
    f(0, path);
    return 0;
}

在這個版本中，我們定義了一個遞迴函式 `f`，它接受當前的層級 `level` 和存儲路徑的陣列 `path`。當 `level` 等於 3 時，表示已經完成了一個完整的組合，此時輸出結果。否則，函式會遍歷當前層級的所有可能值，並遞迴呼叫自身以處理下一層。

### C. 加上邊界條件

為了避免重複的組合，我們需要在遞迴過程中添加邊界條件，確保每一層的選擇不會與前面層級的選擇重複。這是 Backtracking 的關鍵所在。以下是最終版的程式碼：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void f(int level, vector<int>& path) {
    if (level == 3) {
        cout << path[0] << " " << path[1] << " " << path[2] << endl;
        return;
    }

    for (path[level] = 1; path[level] <= 3; path[level]++) {
        // 檢查當前選擇是否已在之前的層級中出現
        if (count(begin(path), begin(path) + level, path[level]) != 0) continue;
        f(level + 1, path);
    }
}

int main() {
    vector<int> path(3);
    f(0, path);
    return 0;
}

在這個版本中，我們在每次選擇新的值之前，使用 `count` 函式檢查該值是否已經出現在之前的層級中。如果已存在，則跳過這個選擇，避免重複。這樣，我們就成功地將 Backtracking 的思想應用到了遞迴解法中，使程式碼更加高效且通用。

### reference

- [【C++ 資料結構與演算法】回溯法 (backtracking)](https://youtu.be/nrHTtjkYEyQ?si=NfshyKpYdkKBOCWb)