C++ 递归回溯算法详解：全排列问题实战

C++ 中实现递归回溯的方法如下：

定义递归函数：首先，定义一个递归函数来解决问题。递归函数的参数可以根据具体问题的需要进行定义。
确定递归结束条件：在递归函数中，需要明确递归的结束条件。一旦满足结束条件，递归将停止。
处理当前层逻辑：在每次递归调用之前，处理当前层逻辑。可以进行一些操作、判断或计算。
进行递归调用：根据具体问题的需要，进行递归调用。通常是修改函数参数，将问题规模缩小，继续递归调用函数本身。
恢复状态：在递归调用返回后，需要恢复状态，以便进行回溯。这通常包括还原参数、清除标记等操作。

下面是一个示例，展示了如何使用递归回溯来解决全排列问题：

#include <iostream>
#include <vector>
using namespace std;

void backtrack(vector<int>& nums, vector<int>& permutation, vector<bool>& used) {
    // 递归结束条件：当排列长度等于原始数组长度时，打印排列结果
    if (permutation.size() == nums.size()) {
        for (int num : permutation) {
            cout << num << ' ';
        }
        cout << endl;
        return;
    }

    for (int i = 0; i < nums.size(); i++) {
        // 如果当前数字已经被使用过，则跳过该数字
        if (used[i]) {
            continue;
        }
        
        // 处理当前层逻辑：将当前数字加入排列，标记为已使用
        permutation.push_back(nums[i]);
        used[i] = true;

        // 递归调用：继续寻找下一个数字
        backtrack(nums, permutation, used);

        // 恢复状态：将当前数字从排列中移除，取消已使用标记
        permutation.pop_back();
        used[i] = false;
    }
}

void permute(vector<int>& nums) {
    vector<int> permutation; // 存储排列结果
    vector<bool> used(nums.size(), false); // 记录数字是否被使用过

    backtrack(nums, permutation, used);
}

int main() {
    vector<int> nums = {1, 2, 3}; // 原始数组
    permute(nums); // 输出全排列结果

    return 0;
}

以上代码演示了如何使用递归回溯来生成全排列。在递归函数backtrack中，通过不断选择未使用过的数字，并将其加入排列中，然后继续递归调用函数本身，直到排列长度等于原始数组长度，即找到一个完整的排列。然后通过恢复状态进行回溯，继续寻找下一个数字。最终，通过调用permute函数，可以得到全排列的结果。