描述
给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）
数据范围：数字个数 0<n≤6
要求：空间复杂度 O(n!)，时间复杂度 O(n!）
示例1
输入：
[1,2,3]
返回值：
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例2
输入：
[1]
返回值：
[[1]]
思路分析：
经典的回溯算法问题——全排列（Permutations）
-
permute方法：这是类的公共方法，接收一个整数数组num作为输入，并返回一个ArrayList<ArrayList<Integer>>类型的列表，其中每个内部列表代表num数组的一个排列。- 初始化一个
ArrayList<ArrayList<Integer>>类型的result列表，用于存储所有排列。 - 初始化一个
LinkedList<Integer>类型的list，用于在回溯过程中构建当前的排列。 - 调用
backTrack方法开始回溯过程。
- 初始化一个
-
backTrack方法：这是一个私有方法，用于递归地生成所有排列。它接收三个参数：-
num：原始整数数组。 -
list：当前正在构建的排列（以链表形式）。 -
result：用于存储所有排列的列表。 -
递归终止条件：如果
list的大小等于num的长度，说明已经构建了一个完整的排列，此时将这个排列（通过new ArrayList<Integer>(list)转换为不可变列表）添加到result中，并返回。 -
递归过程：遍历
num数组中的每个元素，如果当前元素已经存在于list中，则跳过该元素（避免重复排列）。否则，将该元素添加到list中，并递归调用backTrack方法继续构建下一个元素。递归返回后，需要撤销上一步的选择（即移除list中最后添加的元素），以便尝试其他可能的排列。
-
代码：
import java.util.*;
public class Solution {
public ArrayList<ArrayList<Integer>> permute(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
LinkedList<Integer> list = new LinkedList<>();
backTrack(num, list, result);
return result;
}
private void backTrack(int[] num, LinkedList<Integer> list,
ArrayList<ArrayList<Integer>> result) {
if (list.size() == num.length) {
result.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < num.length; i++) {
if (list.contains(num[i])) {
continue;
}
list.add(num[i]);
backTrack(num, list, result);
list.removeLast();
}
}
}
