【Leetcode 热题 100】46. 全排列

问题背景

给定一个不含重复数字的数组 $nums$，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

数据约束

• $1\le nums.length\le 6$
• $-10\le nums[i]\le 10$
• $nums$ 中的所有整数 互不相同

解题过程

回溯真的老大难，排列问题在递归的过程中是不知道之前元素是否被使用的，要用哈希表来判断是不是已经选择过，同时要注意恢复现场。
或者枚举当前位置可选的元素，用集合来判断，要注意避免并发修改异常。

具体实现

选或不选

class Solution {public List<List<Integer>> permute(int[] nums) {int n = nums.length;List<List<Integer>> res = new ArrayList<>();// 流程中答案是直接在对应位置上进行设置的，需要用这种方式定义有初始长度的列表List<Integer> path = Arrays.asList(new Integer[n]);boolean[] onPath = new boolean[n];dfs(0, nums, res, path, onPath);return res;}private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, boolean[] onPath) {if(i == nums.length) {res.add(new ArrayList<>(path));return;}// i 枚举可能位置，j 访问可能元素for(int j = 0; j < nums.length; j++) {if(!onPath[j]) {path.set(i, nums[j]);onPath[j] = true;dfs(i + 1, nums, res, path, onPath);onPath[j] = false;}}}
}

选哪一个

class Solution {public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();Set<Integer> set = new HashSet<>();for(int num : nums) {set.add(num);}dfs(0, nums, res, path, set);return res;}private void dfs(int i, int[] nums, List<List<Integer>> res, List<Integer> path, Set<Integer> set) {if(i == nums.length) {res.add(new ArrayList<>(path));return;}// List 中有重载的 remove 方法，表达不同的删除语义，这里必须用包装类型来遍历for(Integer item : set) {path.add(item);Set<Integer> temp = new HashSet<>(set);temp.remove(item);dfs(i + 1, nums, res, path, temp);path.remove(item);}}
}