AcWing 167. 木棒：心得

dfs的本质：是选择，其核心的for循环就是 把当前位置（状态）面临的所有选择都尝试一遍，每个尝试都是一棵搜索子树（方案的一种情况）。

恢复现场（回溯）
站在求所有方案数的角度（for循环中dfs调用一次，可以理解为产生一次方案，结束后随之恢复）
dfs在搜索方案，即每个方案（解）都是独立，而dfs中的核心部分for循环，就是每个方案的分支，同一层下需要选择每一种分支（可能），这里的恢复现场就起到了至关重要的作用，循环整体上看（同一层），if(!st[i])并不会封锁每次循环，对应每种方案都考虑进去，因为每次循环体的内部都进行了恢复。然而在搜索树的纵向上（同一分支），这里的恢复现场就保证了，不会做出相同的选择。 — 总的来讲，恢复现场保证了各个方案的独立性，已经每种方案内部的不重复性。

如果在寻找方案的同时返回bool，即在判断是否可行，找到可行方案即终止，并非会遍历到所有的方案（只有一直失败，才会一直遍历）。如下：

        if(w[i] + cur_len <= len)
        {
            st[i] = 1;
            if(dfs(u, cur_len + w[i], i + 1)) return 1;
            // return dfs(u, cur_len + w[i], i + 1);  //就算失败了也要恢复现场，恢复现场是必须的。
            st[i] = 0;//恢复现场
        }

·此处dfs返回是否可行，那么当成功时，直接返回即可，不需要会恢复现场，这里会直接返回到最初调用的（最顶层,直接终止），整个dfs直接返回true。–所以这种返回bool类型的dfs，一旦找到 可行方案 就会返回，并非一定搜索全部的解，除非一直没有找到肯行解，那么因为每种解都是独立的，因此失败的时候必须恢复现场，避免影响搜索其他解----— 总的来讲，恢复现场保证了各个方案的独立性，已经每种方案内部的不重复性。

何时回溯（恢复现场）？
他人的解释：
对于dfs什么时候回溯什时候不回溯，我认为取决于题目具体问法，例如方案数这种就表明了，遍历的点可以被选也可以不被选，所以得回溯，而如果是 联通块说明每个点都得选，所以不需要回溯

排列（1-n）

#include<iostream>
using namespace std;

const int N = 10;

int n;
int a[N];
int b[N];
bool st[N];//这个数是否使用过
void dfs(int u)
{
    if(u == n) 
    {
        for(int i = 0; i < n; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i++)
    {
        if(!st[b[i]])
        {
            a[u] = b[i];
            st[b[i]] = 1;
            dfs(u + 1);
            a[u] = 0;//因为是 覆盖 所以 恢复现场可以省略 
            st[b[i]] = 0;
        }

    }

}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        b[i] = i + 1;
    }

    dfs(0);

    return 0;
} 

组合C_n -m（避免重复，认为规定顺序start）

#include<iostream>
using namespace std;

const int N = 10;

int n, m;
int a[N];
int b[N];
bool st[N];
void dfs(int u, int start, int m)
{
    if(u == m) 
    {
        for(int i = 0; i < m; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
        return;
    }

    for(int i = start; i < n; i++)
    {
        if(!st[b[i]])
        {
            st[b[i]] = 1;
            a[u] = b[i];
            dfs(u + 1, i + 1, m);
            a[u] = 0;//因为是 覆盖 所以 恢复现场可以省略 
            st[b[i]] = 0;
        }

    }

}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++)
    {
        b[i] = i + 1;
    }

    dfs(0, 0, m);

    return 0;
}