Permutations 全排列

生成一个整数数组的全排列无重复元素

生成一个整数数组的全排列，并通过一个具体的代码示例来详细讲解整个过程。全排列问题在算法中是一个经典的递归回溯问题，它用于生成给定元素的所有可能排列组合。

一、问题描述

给定一个没有重复元素的整数数组，生成该数组的所有可能排列组合。例如，输入 [1, 2, 3]，输出结果将是：

[1 2 3]
[1 3 2]
[2 1 3]
[2 3 1]
[3 1 2]
[3 2 1]

这个问题可以通过递归和回溯算法来解决。我们逐步交换数组中的元素，然后递归地继续处理数组的剩余部分。当我们处理到数组的最后一个元素时，意味着当前的排列已经生成，应该将其保存。

二、算法思路

1. 递归与回溯：
   • 使用递归来枚举每个位置上可能的元素。
   • 通过交换数组中的元素来创建新的排列。
   • 在每次递归调用完成后，使用回溯（通过再次交换元素恢复原数组）来还原之前的状态。
2. 基线条件：
   • 当递归到数组的最后一个位置时，说明已经生成了一个完整的排列，我们将其添加到结果集中。
3. 结果存储：
   • 我们使用一个二维切片 [][]int 来存储所有生成的排列组合。

三、代码实现

首先定义了生成全排列的函数 permutations，以及用于递归和回溯的辅助函数 backtrace。