第一部分：回溯法 (Backtracking) 的核心本质与模板

回溯法的本质是穷举。它不是在遍历一棵真实存在的树，而是在遍历一棵逻辑上的“决策树”。 它的核心动作是：做选择 -> 递归 -> 撤销选择（回溯）。

C++

void backtrack(当前所处的阶段/深度) {
    if (满足结束条件) {
        记录/输出当前结果;
        return;
    }
    
    for (枚举当前阶段的所有可能选择) {
        if (这个选择合法) {
            做出选择; (记录到路径中，标记为已使用等)
            backtrack(进入下一个阶段);
            撤销选择; (将路径中的记录删除，标记为未使用) // <- 这就是"回溯"的灵魂！
        }
    }
}

1.全排列型 DFS (Permutations)

特点：顺序有关（[1,2] 和 [2,1] 是不同的）。每次都要从头开始找没用过的数字。

C++

const int N = 10;
int path[N];      // 记录当前的排列路径
bool used[N];     // 记录数字是否被使用过
int n = 3;        // 假设对 1, 2, 3 进行全排列
​
void dfs_permutation(int depth) {
    if (depth == n) { // 选够了 n 个数，输出
        for (int i = 0; i < n; ++i) cout << path[i] << " ";
        cout << "\n";
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            path[depth] = i;  // 做出选择
            used[i] = true;   // 标记已使用
            
            dfs_permutation(depth + 1); // 递归进入下一层
            
            used[i] = false;  // 撤销选择（回溯）
        }
    }
}

2. 组合型 DFS (Combinations)

特点：顺序无关（[1,2] 和 [2,1] 视为同一种）。为了避免重复，我们需要按顺序取，比如规定下一个取的数字必须比当前的大。

C++

int path[N];
int n = 4, k = 2; // 从 1~4 中选 2 个数
​
// start: 这一层允许从哪个数字开始选
void dfs_combination(int start, int depth) {
    if (depth == k) { // 选够了 k 个数，输出
        for (int i = 0; i < k; ++i) cout << path[i] << " ";
        cout << "\n";
        return;
    }
    
    // 组合型：从 start 开始枚举，保证选的数字是递增的，避免重复
    for (int i = start; i <= n; ++i) {
        path[depth] = i; // 做出选择
        
        // 递归进入下一层，下一个数必须从 i + 1 开始选
        dfs_combination(i + 1, depth + 1); 
        
        // 组合只需覆盖 path[depth] 的值即可，无需特殊的“撤销”标记
    }
}

3. 子集型 DFS (Subsets)

特点：每个元素只有两种状态：“选”或者“不选”。

C++

int path[N];
int n = 3; // 求 1, 2, 3 的所有子集
​
// i: 当前考虑到了第几个元素
void dfs_subset(int i, int depth) {
    if (i == n + 1) { // 所有元素都考虑完了
        for (int j = 0; j < depth; ++j) cout << path[j] << " ";
        cout << "\n";
        return;
    }
    
    // 选择一：不选第 i 个元素
    dfs_subset(i + 1, depth); 
    
    // 选择二：选第 i 个元素
    path[depth] = i; 
    dfs_subset(i + 1, depth + 1); 
}
//另一种写法
void dfs(int u){
    if(u>n){
        for(int i=1;i<=n;i++){
            if(vis[i]) cout<<i<<" ";
        }
        cout<<"\n";
        return;
    }
    vis[u]=false;
    dfs(u+1);
    vis[u]=true;
    dfs(u+1);
}