c++递归实现全排列

在C++中，递归是一种强大的技术，常用于解决那些可以通过将问题分解为规模更小相同问题来求解的问题，比如生成所有可能的全排列。全排列指的是从给定的一组元素中取出一部分或全部元素的所有不同顺序的排列。

以下是一个简单的C++递归算法，用来生成一个数组（这里假设为整数）的全排列：

#include <iostream>
using namespace std;

// 定义全排列函数
void permute(int arr[], int start, int end) {
    // 基线条件：当起始索引等于结束索引时，我们已经得到了一个完整的排列，所以打印出来
    if (start == end) {
        for (int i = 0; i <= end; ++i)
            cout << arr[i] << " ";
        cout << endl;
    }
    else {
        // 对于每个可能的位置，交换起始位置的元素，然后递归处理剩余的部分
        for (int i = start; i <= end; ++i) {
            swap(arr[start], arr[i]); // 交换元素
            permute(arr, start + 1, end); // 递归调用，移动起始位置
            swap(arr[start], arr[i]); // 回溯：恢复原始状态，以便尝试下一个位置
        }
    }
}

int main() {
    int arr[] = {1, 2, 3};
    int n = sizeof(arr) / sizeof(arr);
    permute(arr, 0, n - 1);
    return 0;
}

当你运行这个程序，会打印出`1 2 3`, `1 3 2`, `2 1 3`, `2 3 1`, `3 1 2`, 和 `3 2 1`这六个全排列。