C++实现一个回溯算法

回溯算法是一种常用的搜索算法，通常用于解决组合问题、排列问题、选择问题等。下面是一个使用C++语言实现的回溯算法示例，用于求解1~n的排列组合问题：

#include <iostream>
using namespace std;

const int N = 10;

int n;  // n个数
int nums[N];  // 数组存储1~n的数
bool used[N];  // 标记数字是否已被选中
int path[N];  // 存储当前排列组合的结果

void backtrack(int depth) {
    if (depth == n) {  // 排列组合完成，输出结果
        for (int i = 0; i < n; i++) {
            cout << path[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!used[i]) {  // 如果数字i未被选中
            path[depth] = nums[i];  // 将数字i加入当前排列组合
            used[i] = true;  // 标记数字i已被选中
            backtrack(depth + 1);  // 递归搜索下一层
            used[i] = false;  // 回溯到上一层，将数字i标记为未被选中
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        nums[i] = i + 1;
    }
    backtrack(0);
    return 0;
}

在该程序中，我们使用`backtrack`函数实现回溯算法。该函数的参数`depth`表示当前排列组合的深度，初始值为0，表示从第一个位置开始排列组合。当`depth`等于`n`时，表示排列组合完成，输出结果。

在每一层循环中，我们枚举当前可选的数字，如果数字`i`未被选中，则将其加入当前排列组合，并标记为已被选中。然后递归搜索下一层，完成搜索后回溯到上一层，将数字`i`标记为未被选中，以便在后续搜索中重新使用。

该算法的时间复杂度为O(n!)，因为总共有n个数字，每个数字有n-1个可选位置，所以排列组合的总数为n * (n-1) * (n-2) * ... * 1 = n!。