46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example, [1,2,3] have the following permutations:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] 全排列没有重复数字

public class Solution { List<List<Integer>> ret = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] vis = new boolean[nums.length]; dfsCore(nums, 0, nums.length); // dfs(nums, 0, nums.length, vis); return ret; } // 使用交换 private void dfsCore(int[] nums, int idx, int len) { if (idx == len) { // 找到转置完成后的解，将其存入列表中 List<Integer> list = new ArrayList<>(); for (int i = 0; i < len; i++) { list.add(nums[i]); } ret.add(list); } // 将当前位置的数跟后面的数交换，并搜索解 for (int i = idx; i < len; i++) { swap(nums, idx, i); // 传入idx+1 dfsCore(nums, idx + 1, len); swap(nums, idx, i); } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } public class Solution { List<List<Integer>> ret = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { boolean[] vis = new boolean[nums.length]; dfs(nums, 0, nums.length, vis); return ret; } // DFS+回溯 private void dfs(int[] nums, int idx, int len, boolean vis[]) { if (tmp.size() == len) { ret.add(new ArrayList<>(tmp)); } for (int i = 0; i < len; i++) { if (vis[i]) continue; // 遇到已经加过的元素就跳过 vis[i] = true; // 加入该元素后继续搜索 tmp.add(nums[i]); // 可以不传i+1参数，但是递归次数增多 dfs(nums, i + 1, len, vis); tmp.remove(tmp.size() - 1); vis[i] = false; } } }

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations:

[ [1,1,2], [1,2,1], [2,1,1] ]

全排列有重复数字

判断逻辑也可以，跳过相同循环

if (vis[i] || (i > 0 && nums[i - 1] == nums[i]&& !vis[i - 1]))                 continue;

public class Solution { List<List<Integer>> ret = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { boolean[] vis = new boolean[nums.length]; // 排序 Arrays.sort(nums); dfs(nums, 0, nums.length, vis); return ret; } // DFS+回溯 private void dfs(int[] nums, int idx, int len, boolean vis[]) { if (tmp.size() == len) { ret.add(new ArrayList<>(tmp)); } for (int i = 0; i < len; i++) { if (vis[i]) continue; // 遇到已经加过的元素就跳过 vis[i] = true; // 加入该元素后继续搜索 tmp.add(nums[i]); // 可以不传i+1参数，但是递归次数增多 dfs(nums, i + 1, len, vis); tmp.remove(tmp.size() - 1); vis[i] = false; /// // 跳过本轮的重复元素，确保每一轮只会加unique的数字 while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++; } } } 最新测试用例添加了 字典序，此方法不过,

List<List<Integer>> ret = new ArrayList<>(); List<Integer> tmp = new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { Arrays.sort(nums); dfsCore(nums, 0, nums.length); return ret; } // 使用交换 private void dfsCore(int[] nums, int idx, int len) { if (idx == len) { // 找到转置完成后的解，将其存入列表中 List<Integer> list = new ArrayList<>(); for (int i = 0; i < len; i++) { list.add(nums[i]); } ret.add(list); } // 将当前位置的数跟后面的数交换，并搜索解 for (int i = idx; i < len; i++) { /*if (i > idx && nums[i] == nums[i - 1]) continue;*/ swap(nums, idx, i); // 传入idx+1 dfsCore(nums, idx + 1, len); swap(nums, idx, i); while (i < nums.length - 1 && nums[i] == nums[i + 1]) i++; } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }