46. 全排列

原题链接

题目：

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

题解1：回溯法(递归DFS)

主要流程：

每个状态结点的信息包含 输入数组，结果集，使用标记数组，当前列表

这里注意在每次递归搜索完成后需要恢复状态，撤销之前的操作，避免影响其他结点

具体搜素过程图参考如下：

在具体代码中体现的状态重置，就是在递归后加上对状态的恢复。由于是求全排列，每个数只能使用一次，所以这里主要涉及到的状态恢复是每次递归完成后对标记数组 boolean[] used 的状态恢复，即回退操作。

代码：

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); findArrange(nums, res, used, new ArrayList<>()); return res; } //递归函数，参数有输入数组，结果集，使用标记数组，当前列表 public void findArrange(int[] nums, List<List<Integer>> res, boolean[] used, List<Integer> list) { //递归终止判断 if (list.size() == nums.length) { res.add(list); return; } else { for (int i = 0; i < nums.length; i++) { if (!used[i]) {//未被搜索过 used[i] = true; List<Integer> tempList = new ArrayList<>(list); tempList.add(nums[i]); findArrange(nums, res, used, tempList); used[i] = false;//最后需要将状态改为原来状态回溯 } } } } }

题解2：题解1的不用状态恢复版本

主要思路：

每次都创建一个新的数组来保存遍历过的数，但这样空间开销会更大该方法每一次尝试都「复制」，则不需要回溯，即不需要状态恢复大部分代码类似题解1

代码：

class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); boolean[] used = new boolean[nums.length]; Arrays.fill(used, false); findArrange(nums, res, used, new ArrayList<>()); return res; } //递归函数，参数有输入数组，结果集，使用标记数组，当前列表 public void findArrange(int[] nums, List<List<Integer>> res, boolean[] used, List<Integer> list) { //递归终止判断 if (list.size() == nums.length) { res.add(list); return; } else { for (int i = 0; i < nums.length; i++) { if (!used[i]) {//未被搜索过 //在每个结点状态都创建一个状态数组，这样不用在递归结束后恢复状态 boolean[] tempUsed = new boolean[used.length]; System.arraycopy(used, 0, tempUsed, 0, used.length); tempUsed[i] = true; List<Integer> tempList = new ArrayList<>(list); tempList.add(nums[i]); findArrange(nums, res, tempUsed, tempList); } } } } } 参考题解： 回溯算法入门级详解 + 练习（持续更新）