回溯法实例 c++实现

回溯法（Backtracking）是一种暴力搜索的算法，常应用于求解一些组合问题，比如八皇后问题、0/1 背包问题、图的着色问题等。该算法在搜索过程中，每次都尝试当前所有可能的分支，直到找到一个符合条件的结果或者所有的分支都被尝试过。

下面是一个简单的回溯法实例，用来求解 1~n 的全排列：

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, int n, vector<vector<int>>& res) {
    if (path.size() == n) {  // 如果 path 中的元素个数已经达到了 n，说明已经找到了一组解
        res.push_back(path);  // 将 path 添加到结果集中
        return;
    }
    for (int i = 0; i < n; i++) {  // 遍历所有可能的分支
        if (!used[i]) {  // 如果当前数字没有被使用过
            path.push_back(nums[i]);  // 添加当前数字到 path 中
            used[i] = true;  // 标记当前数字已经被使用
            backtrack(nums, path, used, n, res);  // 继续进入下一层递归
            used[i] = false;  // 回溯到上一层时，需要将当前数字的使用状态置为未使用
            path.pop_back();  // 回溯到上一层时，也需要将当前数字从 path 中删除
        }
    }
}

vector<vector<int>> permute(int n) {
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> used(n, false);
    backtrack(nums, path, used, n, res);
    return res;
}

int main() {
    int n = 3;
    vector<vector<int>> res = permute(n);
    for (auto& r : res) {
        for (int i = 0; i < n; i++) {
            cout << r[i] << " ";
        }
        cout << endl;
    }
    return 0;
}

在上述代码中，backtrack 函数用来进行递归搜索，其中 nums 存储了待排列的数字，path 存储当前已经选择的数字，used 数组表示数字是否被使用过。当 path 的长度等于 n 时，说明已经找到了一组解，将其添加到结果集中。在遍历所有可能的分支时，需要判断当前数字是否已经被使用过，如果没有，则将其添加到 path 中，并继续进入下一层递归。当回溯到上一层时，需要将当前数字的使用状态置为未使用，并将其从 path 中删除，继续遍历其他分支。最终返回所有的解。