用c++写一个程序，输出一个数组n个元素的全排列，描述算法基本思想，并给出程序

在C++中，我们可以使用递归的方式来生成数组的全排列。基本思想是利用回溯法，对于每一个未排列的位置，将当前位置的所有数作为“第一个”位置，然后对剩余的元素进行递归排列，直到所有位置都被遍历过。这里是一个简单的示例：

#include <iostream>
#include <vector>

// 用于存储临时结果
std::vector<int> temp;

// 排列函数
void permute(int arr[], int l, int r) {
    if (l == r)
        std::cout << "[" << arr[l] << "]" << std::endl;
    else {
        for (int i = l; i <= r; ++i) {
            // 交换arr[l]和arr[i]
            std::swap(arr[l], arr[i]);
            
            // 递归处理剩余的元素
            permute(arr, l+1, r);
            
            // 恢复状态，回溯
            std::swap(arr[l], arr[i]); // 回溯操作，将原位置的元素放回原来的位置
        }
    }
}

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

    std::vector<int> arr(n);
    std::cout << "请输入" << n << "个元素: ";
    for (int i = 0; i < n; ++i) {
        std::cin >> arr[i];
    }

    // 开始排列
    permute(arr, 0, n - 1);

    return 0;
}

在这个程序中，用户首先输入数组的长度和元素，然后`permute`函数会按照上述描述的过程生成并打印出所有的排列。