用c++写一个程序，输出一个数组n个元素的全排列，描述算法基本思想，并给出程序，不使用向量。请给出正确可运行的代码

要编写一个C++程序生成一个整数数组的全排列，我们可以使用递归回溯法。基本的思想是对于每一个位置，我们都尝试将剩余数字的一个作为当前位置的值，然后对剩余的数字继续进行相同的操作，直到所有位置都被填满。当所有位置都填完之后，就得到了一个排列。

下面是一个简单的C++代码实现，它不使用向量，而是直接用数组存储：

#include <iostream>

// 函数声明用于保存当前排列的数组
void generatePermutations(int arr[], int n, int index = 0);

int main() {
    int n;
    std::cout << "请输入数组长度: ";
    std::cin >> n;

    // 创建一个大小为n的数组
    int array[n];
    for (int i = 0; i < n; i++) {
        std::cout << "请输入第" << i + 1 << "个元素: ";
        std::cin >> array[i];
    }

    // 开始生成全排列
    generatePermutations(array, n);
    return 0;
}

// 递归函数，生成数组的排列
void generatePermutations(int arr[], int n, int index) {
    if (index == n) {
        // 当索引达到n，表示完成了一次排列，打印出来
        for (int i = 0; i < n; i++) {
            std::cout << arr[i] << " ";
        }
        std::cout << std::endl;
    } else {
        // 对每个未放置的元素进行尝试
        for (int i = index; i < n; i++) {
            // 交换arr[index] 和 arr[i]
            std::swap(arr[index], arr[i]);

            // 继续递归处理剩余元素
            generatePermutations(arr, n, index + 1);

            // 撤销当前交换，恢复到上一步状态
            std::swap(arr[index], arr[i]);
        }
    }
}