题目
题目来源leetcode
leetcode地址：46. 全排列，难度：中等。
题目描述(摘自leetcode)：
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 示例 2： 输入：nums = [0,1] 输出：[[0,1],[1,0]] 示例 3： 输入：nums = [1] 输出：[[1]] 提示： 1 <= nums.length <= 6 -10 <= nums[i] <= 10 nums 中的所有整数 互不相同
本地调试代码：
public class Solution { public List<List<Integer>> permute(int[] nums) { ... } public static void main(String[] args) { final List<List<Integer>> permute = new Solution().permute(new int[]{1, 2, 3}); System.out.println(permute); } }
题解
NO1：回溯
思路：根据题意画出对应回溯情况的二叉树，确定边界条件（出口）以及一些必要的辅助数组、集合等即可。
所需要的一些必要条件如(对应该题)：出口（深度都为3），收集全排序的集合(res)，深搜+回溯产生出来的过程结果集（path），还有最核心的一个问题就是在进行深搜过程中如何排除掉已添加到path的某个结果值？可使用一个与nums数组同大小的状态数组来进行记录，在深搜过程中枚举判断即可！
根据图来推出所需要的情况及条件，那么我们就可以来编写递归的函数方法了，对应参数也就是上面举出的。
代码：
public List<List<Integer>> permute(int[] nums) { //全排列结果集、一组结果集、标记访问数组（默认为false） List<List<Integer>> res = new ArrayList<>(); List<Integer> path = new ArrayList<>(); boolean[] visitArr = new boolean[nums.length]; recall(nums,path,0,visitArr,res); return res; } /** * 回溯求得全排列 * @param nums 待全排列数据集集合 * @param path 待添加入的一组数据 * @param depth 深度 * @param visitArr 标记是否访问数组 * @param res 全排列结果集 */ private void recall(int[] nums, List<Integer> path, int depth, boolean[] visitArr, List<List<Integer>> res) { //出口条件，到达指定的深度结束 if (depth == nums.length){ res.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++) { //若是没有访问过的情况 if (!visitArr[i]){ path.add(nums[i]); visitArr[i] = true; recall(nums,path,depth + 1,visitArr,res); //回溯 path.remove(path.size() - 1); visitArr[i] = false; } } }
