# DFS

• 深度優先搜尋（DFS）是窮舉的一種方法，屬於暴力搜尋（簡稱暴搜）的一種，
用來窮舉多重選擇下的所有可能情形。
• 它會依序窮舉每一層的所有可行選擇，對於每個選擇都會先行窮舉後續的所有分歧
• DFS 由於其搜尋空間呈指數成長，對於大半的題目複雜度都會過高，
• 但幾乎能暴搜出任何問題的正解，可用於獲取子任務分數，
• 或者用來搜小測資來找規律、或驗證其它做法的答案等各種用途。

## 實作

• 儘管多層的巢狀迴圈也能做到一樣的事，但彈性不夠。
• 因此使用函數遞迴的方式，每次函數呼叫會是一層
• 決定選項之後，遞迴呼叫自己來決定下一層。
• 每次走到最下層，代表找出了一種情況，結算後退回上一層

可以把多層迴圈其中單獨一層出來看，那麼他所做的事就是(對該層的每個選項，都往下一層總共有幾種可能情況)，這樣每層迴圈的邏輯都很相似，可寫成函式來呼叫

## 流程

流程上對於第 i 層大概會是：
如果是最下層
->結算
如果不是最下層
->選擇一個未選過的選項，遞迴呼叫第 i+1 層來決定後續選項
反覆以上動作，直到不存在未選過的選項為止
• 由於每層又會遞迴往下呼叫，因此呼叫第 0 層，就會一路決定到最下層了。

## DFS 與遞迴的差異

廣義上的遞迴是函數自己呼叫自己都算，因此會說 DFS 實作依賴於遞迴。
但是和一般遞迴式的求解方式不同，DFS 畢竟是搜尋，
遞迴只是為了走遍所有選項所形成的樹狀圖而已。

在演算法的設計理念中，是屬於回朔法，在不確定每個選項是我們要或不要的東西時，那就每種都選擇看，選擇看完結果後，再回朔並改選別的選項看看不同結果

• 除了沒有明確的遞迴式，另個最大的差別是不回傳答案，
而是在最底層對每種可能性做必要的處理。
這個處理可能是輸出，統計或者其它用途。

## 所有組合

輸入兩整數 N 和 M，輸出所有從 1 到 N 中取 M 個數字的情況(保持嚴格遞增)。

• 將「選擇」視為「集合」，只要保證所有選擇皆符合「嚴格遞增」的性質，
就不會存在只有順序不同的集合。
• 為了保持嚴格遞增，每次選中的數字必須比上一個數字大，
這導致當前的選擇會影響後續的選項，狀態必須傳遞下去。
• 需要將每一層的選擇列出，因此要記錄每一層的選擇。

#include <bits/stdc++.h>
using namespace std;
int n,m;
int res[1000];
//第depth層,最小選項為start
void dfs(int depth,int start){
    if(depth==m){//終止條件
        for(int i=0;i<m;i++){
            cout<<res[i]<<" ";
        }
        cout<<"\n";
        return ;
    }
    for(int i=start;i<=n;i++){
        //紀錄第depth層的選擇
        res[depth]=i;
        dfs(depth+1,i+1);
    }
}
int main(){
    cin>>n>>m;
    dfs(0,1);
return 0;
}

## 位元枚舉
給你一個集合,請輸出所有所有子集合
### dfs版

#include <bits/stdc++.h>
using namespace std;

int n;
int s[1000];
bool used[1000];
void dfs(int depth) {
    if (depth == n) {
        for (int i = 0; i < n; i++)
            if (used[i]){
                cout << s[i] << " ";
            }
        cout << "\n";
        return;
    }
    used[depth] = true;
    dfs(depth + 1);
    used[depth] = false;
    dfs(depth + 1);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) cin >> s[i];
    dfs(0);
}

每個數字取或不取，可以對應到0還有1
因此，我們可以使用數字的二進位表示法來枚舉
EX
S = {1, 2, 3}，因為|S|=3，因此我們需要
000、001、010、011、100、101、110、111，這些數字
### 位元運算版

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector <int> s(n);
    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if ((i >> j) & 1)
                cout << s[j] << " ";
        }
        cout << "\n";
    }
}

## 所有排列
輸入正整數 N 輸出 1 到 N 的所有排列

前面的課程有學到如何用next_permutation求出所有排列，不過今天我們用dfs來枚舉所有可能
做法是用一個陣列記錄每個數字是否被選過
在窮舉選項時，只能選擇前幾層尚未被選取過的選項。

#include <bits/stdc++.h>
using namespace std;
int n;
int res[1000];
bool used[1000];
void dfs(int depth){
    if(depth==n){//終止條件
        for(int i=0;i<n;i++){
            cout<<res[i]<<" ";
        }
        cout<<"\n";
        return ;
    }
    for(int i=1;i<=n;i++){
        //選擇未被選過的選項
        if(!used[i]){
            //標記為已被選取
            used[i]=true;
            res[depth]=i;
            dfs(depth+1);
            //更換選項,取消標記
            used[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
return 0;
}

## 全排列的重複防止

求全排列的問題，在元素重複時，會產生重複排列。
如果對重複的元素偷偷上個標記，就能了解是怎麼回事。
例如 1123 的排列會產生以下重複：

21(a)31(b)
21(b)31(a)

觀察性質，會發現問題在於對同個位置放了 1a 之後，又放上 1b。這兩種到放完 1 時完全
相同，等於是對兩種相同情形各自向下展開，那麼自然也會得到重複的結果。

### 方法:保證只放同種類第一個

如果保持排序，可以把同種類的排在一起，也就是同類會相同出現，所以只需判斷當前元素，是否和上一個選擇的元素相同就好了

#include <bits/stdc++.h>
using namespace std;
int n;
int arr[1000];
int res[1000];
bool used[1000];
int tbl[1000005]={-1};//儲存該數字上一次出現的位置
void dfs(int depth){
    if(depth==n){
        for(int i=0;i<n;i++){
            cout<<res[i]<<" ";
        }
        cout<<"\n";
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!used[i] && tbl[arr[i]]<i){
            int l=tbl[arr[i]];
            used[i]=true;
            res[depth]=arr[i];
            tbl[arr[i]]=i;
            dfs(depth+1);
            tbl[arr[i]]=l;
            used[i]=false;
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>arr[i];
    dfs(0);
return 0;
}

## 剪枝

• 剪枝是 DFS 的重要技巧之一，對能夠提早確定「不需要再往下看也知道結果」的狀況，
不再往下看後續的分歧，直接重新選擇。
• 如同一棵樹剪去一個分枝時，會連同該分枝上的其它枝葉一併剪下一般，
會將後續的分歧全部捨棄，節省掉後續的所有計算量。
• 善用這個技巧，能大幅降低搜尋範圍，甚至可能改變複雜度。
不過改變後的複雜度不易估計，每道題能剪的條件沒什麼共通性，
剪錯還可能把答案一併剪了，是相當不易掌握的技巧。