# 暴搜 ( Brute force) 和 回溯演算法 ( Backtracking )
###### tags: `Note` `recursion` `backtracking`

# 一、遞迴
* 遞迴是暴力列舉需要用到的技巧。遞迴需要兩個條件，一個是需要重複執行函式本身，另一個是需要有中止條件。
* 遞迴的原理簡而言之，是利用**函式堆疊**的概念。每一次遞迴就像是放入 stack 中，並在中止條件後依序回到第一層函式。

### 例題：
> 1. 幸運數字：https://hackmd.io/@rickrool/BJ0JAwyAi
> 2. DF-expression：https://hackmd.io/@rickrool/SyYFLeO4n
> 3. 石窟探險：https://hackmd.io/@rickrool/rJRavZdW3

## 二、暴力搜尋法
* 雖然是一種效率很低的作法，但由於直覺，且實作起來容易，對於某些測資較弱或時限較寬的題目來說依然有效。
* 暴力搜尋並不是無腦列舉所有情形，一定的思考和分解問題可以大大提升程式的可讀性和效率。
* 暴搜是許多演算法，如：DP、Greedy 等等的基礎概念。在題目想不出來時，思考暴力搜尋的方法可能會使上述演算法的實現更容易。
> 例題：
> 1 . 子集合乘積：https://hackmd.io/@rickrool/SJQWDtl4n
> 2 . Generate Parentheses：https://hackmd.io/@rickrool/ryvsF9lVn
> 3 . 12406 - Help Dexter：https://hackmd.io/@rickrool/ryXl6hJSn
---

## 三、回溯演算法 ( backtracking )
* 其實和暴搜有點像，但 backtracking 加入了一點**樹**的概念( 至少我是這樣理解 )，某些情況下可以大大加速程式運行。
* 和直接列舉所有情況的暴搜不同，回溯演算法的機制讓它不會枚舉到錯誤的數值，意即：可以到遞迴終點的情況一定會是正確答案。

#### 範例 1：[51. N-Queens](https://leetcode.com/problems/n-queens/)

:::spoiler <b style="color:white">Code</b>

class Solution {
public:
    vector<vector<string>> res;
    bool can_we_place(vector<string> &plate,int x,int y,int n){
        int r=y-1,k=y-1;
        int dx=x-1;
        int dy=y-1;
        bool sta=true;
        for (int i=0;i<n;i++){
            if (plate[y][i]=='Q') {
                return false;
            }
        }
        for (int i=0;i<y;i++){
            if (plate[i][x]=='Q') return false;
        }
        for (int i=x+1;i<n;i++){
        if (dy<0) break;
        if (plate[dy][i]=='Q') return false;
        dy--;
    }

        for (int i=y-1;i>=0;i--){
        if (dx<0) break;
        if (plate[i][dx]=='Q') {
            return false;
        }
        dx--;
    }
        return sta;
    }
    void find(vector<string> &plate,int n,int layer){
        if (layer==n){
            res.push_back(plate);
            return;
        }

        for (int i=0;i<n;i++){
            
                if (!can_we_place(plate,i,layer,n)){
                    continue;
                }
                plate[layer][i]='Q';
                find(plate,n,layer+1);
                plate[layer][i]='.';
            
            
        }

        
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> table(n,string(n,'.'));
        find(table,n,0);
        cout<<res.size()<<endl;
        return res;
    }
};

:::
* 這裡將棋盤看成是一顆「<b>樹</b>」，如果是一個 8X8 的棋盤，他就有八層深度，每層只能放置一個**合法的**皇后。
* 函式 find( 遞迴 ) 中的 for 迴圈扮演了重要的角色：將不符合條件的情況直接跳過，不讓他進到遞迴終點 ( 樹的最後一層 )。這樣可以有效避免列舉棋盤的所有情況，達成「剪枝」的目的。
#### 註：N皇后問題的更快速解法
[這篇文章](https://zhuanlan.zhihu.com/p/22846106)提到了位元運算的解法。雖然速度更快，但程式碼難懂，這裡貼出來欣賞用。

#### 範例二：[47. Permutations II](https://leetcode.com/problems/permutations-ii/)

筆記：https://hackmd.io/@rickrool/Sy1kRsfV2

* 這題的特點是測資**含有重複元素**，如果用一般的暴搜，除了會 TLE，也會出現一堆重複情況。
* 算是一題很好拿來練習剪枝技巧的題目。