[leetcode]47. Permutations全排列(给定序列有重复元素)

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

Example:

Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ]

 

题意：

打印全排列，注明了给定序列可含有重复元素

 

Solution1: Backtracking

 

code

1 class Solution { 2 public List<List<Integer>> permuteUnique(int[] nums) { 3 List<List<Integer>> list = new ArrayList<>(); 4 List<Integer> path = new ArrayList<>(); 5 Arrays.sort(nums); // necessary！因为后面要查重 6 dfs(list, path, nums, new boolean[nums.length]); 7 return list; 8 } 9 10 private void dfs(List<List<Integer>> list, List<Integer> path, int [] nums, boolean [] used){ 11 if(path.size() == nums.length){ 12 list.add(new ArrayList<>(path)); 13 return; 14 } 15 for(int i = 0; i < nums.length; i++){ 16 if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue; 17 used[i] = true; //标记用过 18 path.add(nums[i]); 19 dfs(list, path, nums, used); 20 used[i] = false; //恢复default值 21 path.remove(path.size() - 1); 22 } 23 } 24 }

 

转载于:https://www.cnblogs.com/liuliu5151/p/10708510.html

相关资源：数据结构—成绩单生成器