47. 全排列 II

描述

给定一个可包含重复数字的序列 

nums

 ，按任意顺序 返回所有不重复的全排列。

链接

47. 全排列 II - 力扣（LeetCode） (leetcode-cn.com)

解法

1 class Solution {
 2     //存放结果
 3     List<List<Integer>> result = new ArrayList<>();
 4     //暂存结果
 5     List<Integer> path = new ArrayList<>();
 6 
 7     public List<List<Integer>> permuteUnique(int[] nums) {
 8         boolean[] used = new boolean[nums.length];
 9         Arrays.fill(used, false);
10         Arrays.sort(nums);
11         backTrack(nums, used);
12         return result;
13     }
14 
15     private void backTrack(int[] nums, boolean[] used) {
16         if (path.size() == nums.length) {
17             result.add(new ArrayList<>(path));
18             return;
19         }
20         for (int i = 0; i < nums.length; i++) {
21             // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
22             // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
23             // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
24             if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
25                 continue;
26             }
27             //如果同⼀树⽀nums[i]没使⽤过开始处理
28             if (used[i] == false) {
29                 used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树支重复使用
30                 path.add(nums[i]);
31                 backTrack(nums, used);
32                 path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
33                 used[i] = false;//回溯
34             }
35         }
36     }
37 }      

参考

 Carl