用C++详细写一个回溯算法

回溯算法是一种搜索算法，常用于求解一些组合问题，如排列、组合、子集等。下面是一个用 C++ 实现的排列问题的回溯算法。

#include <iostream>
#include <vector>

using namespace std;

// 判断是否为合法解
bool is_valid(vector<int>& solution) {
    for (int i = 0; i < solution.size(); i++) {
        for (int j = i + 1; j < solution.size(); j++) {
            if (solution[i] == solution[j]) {
                return false;
            }
        }
    }
    return true;
}

// 回溯算法
void backtracking(vector<int>& nums, vector<int>& solution, vector<vector<int>>& result) {
    // 到达叶子节点，判断是否为合法解
    if (solution.size() == nums.size()) {
        if (is_valid(solution)) {
            result.push_back(solution);
        }
        return;
    }

    // 对于每个节点，枚举所有可选的决策
    for (int i = 0; i < nums.size(); i++) {
        // 如果当前元素已经在解中，跳过
        if (find(solution.begin(), solution.end(), nums[i]) != solution.end()) {
            continue;
        }
        // 做出决策
        solution.push_back(nums[i]);
        // 递归进入下一层决策树
        backtracking(nums, solution, result);
        // 撤销决策
        solution.pop_back();
    }
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<int> solution;
    vector<vector<int>> result;
    backtracking(nums, solution, result);

    // 输出所有解
    for (auto& r : result) {
        for (auto& n : r) {
            cout << n << " ";
        }
        cout << endl;
    }

    return 0;
}

在这个例子中，我们要求给定整数集合 {1, 2, 3} 的所有排列。is_valid 函数用来判断当前解是否为合法解，backtracking 函数是回溯算法的核心部分，它用来递归地搜索所有可能的解。最后，我们将所有解存储在 result 中，并输出它们。

注意，在回溯算法中，我们需要在做出决策之后，递归地进入下一层决策树；在回溯之前，需要撤销当前决策，回到上一层决策树继续搜索。这是回溯算法的基本操作，也是实现回溯算法的关键。