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

  • 输入：nums = [1,1,2]
  • 输出：
  • [[1,1,2],
  • [1,2,1],
  • [2,1,1]]

示例 2：

  • 输入：nums = [1,2,3]
  • 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

    解法1：回溯+剪枝，时间复杂度o(n)，空间复杂度o(n)

  1. 对当前数组排序，方便后面去重
  2. 设置一个布尔类型的数组isVisted，判断当前数字是否被使用过
  3. 设置depth深度，深度达到nums.length时，递归结束

  4. 回溯：在循环内，i从0到nums.length，

    1. 每次开始时判断当前字符是否被用过，如果被使用过则直接到下一次循环；判断前一个字符是否跟当前字符一样，如果一样则跳过

    2. 每次递归depth+1，且当前字符加入到list，每次结束时list删除最后一个字符

      1. class Solution {
      2. public List<List<Integer>> permuteUnique(int[] nums) {
      3.   List<List<Integer>> res = new ArrayList<>();
      4.   if(nums.length == 0)
      5.      return res;
      6.   int n = nums.length;
      7.   Arrays.sort(nums);
      8.   boolean []isVisted = new boolean[n];
      9.   List<Integer> list = new ArrayList<>();
      10.   dfs(0,nums,res,list,isVisted);
      11.   return res;
      12. }
      14. public void dfs(int depth,int[] nums,List<List<Integer>> res,List<Integer> list,boolean []isVisted ){
      15.   if(depth == nums.length){
      16.       res.add(new ArrayList<>(list));
      17.   }
      18.   for(int i = 0 ; i < nums.length;i++){
      19.       if(!isVisted[i]){
      20.           if(i > 0 && isVisted[i-1] == true && nums[i] == nums[i - 1]){
      21.               continue;
      22.           }
      23.           list.add(nums[i]);
      24.           isVisted[i] = true;
      25.           dfs(depth + 1,nums,res,list,isVisted);
      26.           isVisted[i] = false;
      27.           list.remove(list.size() - 1);
      28.       }
      29.   }
      30. }
      31. }