【LeeCode】47. 全排列 II

【题目描述】

给定一个可包含重复数字的序列 ​​nums​​ ，按任意顺序 返回所有不重复的全排列。

​​​​​https://leetcode.cn/problems/permutations-ii/​​​

对比：​​【LeeCode】46. 全排列(不含重复)​​​

【示例】

【代码】​​代码随想录​​

package com.company;

import java.util.*;

// 2022-02-07
class Solution {

//存放结果
List<List<Integer>> result = new ArrayList<>();
//暂存结果
List<Integer> path = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtrace(nums, used);
System.out.println(result);
return result;

    }

private void backtrace(int[] nums, boolean[] used) {
if (path.size() == nums.length){
result.add(new ArrayList<>(path));
return;
        }
for (int i = 0; i <nums.length; i++){
// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
continue;
            }

if (used[i] == false){
used[i] = true; //标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
path.add(nums[i]);
backtrace(nums, used);
path.remove(path.size() - 1); //回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
used[i] = false;
            }
        }
    }
}

public class Test {
public static void main(String[] args) {
new Solution().permuteUnique(new int[]{1, 1, 2});  // 输出：[[1,1,2], [1,2,1], [2,1,1]]
new Solution().permuteUnique(new int[]{1, 2, 3});  // 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
    }
}