【Day 82 】2022-06-21 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

• 回溯
• 数组
• 剪枝

  题目描述

  
  给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1]

[JiangWenqi]

class Solution {
 private:
  vector<vector<int>> res;
  vector<int> path;
  vector<bool> visited;
  void dfs(int start, vector<int>& nums) {
    if (start == nums.size()) {
      res.push_back(path);
      return;
    }
    for (int i = 0; i < nums.size(); i++) {
      if (!visited[i]) {
        // same with the previous number and the previous one wasn't visited
        if (i && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
        visited[i] = true;
        path[start] = nums[i];
        dfs(start + 1, nums);
        visited[i] = false;
      }
    }
  }

 public:
  vector<vector<int>> permuteUnique(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    path.resize(n);
    visited.resize(n, false);
    dfs(0, nums);
    return res;
  }
};

[MichaelXi3]

Idea

回溯剪枝

Code

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] isVisited = new boolean[nums.length];  

        // Special case
        if (nums.length == 0 || nums == null) { return res;}

        backTrack(list, res, nums, isVisited);
        return res;
    }

    private void backTrack(List<Integer> list, List<List<Integer>> res, int[] nums, boolean[] isVisited) {
        // Base case
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if (list.size() > nums.length) {
            return;
        }

        // DFS
        for (int i=0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1] && !isVisited[i]) { continue;}
            if (isVisited[i]) { continue;}
            list.add(nums[i]);
            isVisited[i] = true;
            backTrack(list, res, nums, isVisited);
            list.remove(list.size()-1);
            isVisited[i] = false;
        }
    }
}

[taojin1992]

/*
## Evaluation: 

n = nums.length

## Time:

we have n! permutations (assume there are no duplicates, worst case), n! = number of leaves in our recursion tree. For each permutation, we need to copy and paste the curList of length n into the result, therefore, O(n! * n)
+

total number of nodes in the tree: depth n * max nodes in one level (n!)

+ O(nlogn)

= O(nlogn) + O(n! * n)

## Space:
stack depth: O(n)
visited array (boolean): O(n)
curList max/final len: O(n)
output: O(n! * n) numbers

sum up to O(n! * n). 

*/

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        dfs(nums, res, new ArrayList<Integer>(), visited);
        return res;
    }

    private void dfs(int[] nums, List<List<Integer>> res, List<Integer> status, boolean[] visited) {
        if (status.size() == nums.length) {
            res.add(new ArrayList<>(status));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 0 1 2 3 4
            // 2 2 3 3 3
            if (i >= 1 && nums[i] == nums[i-1] && visited[i - 1]) {
                continue;
            }
            if (!visited[i]) {
                status.add(nums[i]);
                visited[i] = true;
                dfs(nums, res, status, visited);
                status.remove(status.size() - 1);
                visited[i] = false;
            }
        }

    }
}

[577961141]

func permuteUnique(nums []int) (ans [][]int) { sort.Ints(nums) n := len(nums) perm := []int{} vis := make([]bool, n) var backtrack func(int) backtrack = func(idx int) { if idx == n { ans = append(ans, append([]int(nil), perm...)) return } for i, v := range nums { if vis[i] || i > 0 && !vis[i-1] && v == nums[i-1] { continue } perm = append(perm, v) vis[i] = true backtrack(idx + 1) vis[i] = false perm = perm[:len(perm)-1] } } backtrack(0) return }

[xingchen77]

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]

        self.backtrack([], nums, check)
        return self.res

    def backtrack(self, sol, nums, check):
        if len(sol) == len(nums):
            self.res.append(sol)
            return

        for i in range(len(nums)):
            if check[i] == 1:
                continue
            if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:
                continue
            check[i] = 1
            self.backtrack(sol+[nums[i]], nums, check)
            check[i] = 0

[wychmod]

思路

每次交换位置，再还原现场

代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def process(nums, index, ans):
            if len(nums) == index:
                # 注意数组是引用类型
                cop = nums.copy()
                if cop not in ans:
                    ans.append(cop)
            else:
                for i in range(index, len(nums)):
                    nums[index], nums[i] = nums[i], nums[index]
                    process(nums, index+1, ans)
                    nums[index], nums[i] = nums[i], nums[index]

        process(nums, 0, ans)
        return ans

[Geek-LX]

6.21

思路：剪枝、回溯

代码：

class Solution:
    def backtrack(numbers, pre):
        nonlocal res
        if len(numbers) <= 1:
            res.append(pre + numbers)
            return
        for key, value in enumerate(numbers):
            if value not in numbers[:key]:
                backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

    res = []
    if not len(nums): return []
    backtrack(nums, [])
    return res

复杂度分析

[houmk1212]

class Solution {
    boolean[] visit;
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        visit = new boolean[n];
        Arrays.sort(nums);
        dfs(nums, new ArrayList<>(), visit);
        return res;
    }

    public void dfs(int[] nums, List<Integer> path, boolean[] visit) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1] && !visit[i] && visit[i-1]) {
                continue;
            }
            if (!visit[i]) {
                visit[i] = true;
                path.add(nums[i]);
                dfs(nums, path, visit);
                path.remove(path.size() - 1);
                visit[i] = false;
            }
        }
    }
}

[maggiexie00]

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    ans=[]
    n=len(nums)

    def back_track(tmp,depth,used):         
        if depth==n:
            ans.append(tmp)
            return

        for i in range(n):
            if used[i]==1:
                continue
            if i>0 and used[i-1]==0 and nums[i]==nums[i-1]:
                continue                

            used[i]=1
            back_track(tmp+[nums[i]],depth+1,used)
            used[i]=0

    nums.sort()
    back_track([],0,[0]*n)
    return ans

[ShawYuan97]

思路

回溯+剪枝

关键点

• 回溯

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
        给定一个包含重复数字的序列，返回所有不重复的全排列

        回溯+剪枝
        """
        nums.sort()
        res = []
        def backtrack(nums,pre_list):
            if len(nums) <=0:
                res.append(pre_list.copy())
            else:
                for i in range(len(nums)):
                    # 排序后去重
                    if i > 0 and nums[i] == nums[i-1]:
                        continue
                    # 使用copy防止传列表的地址
                    p_list = pre_list.copy()
                    p_list.append(nums[i])
                    left_nums = nums.copy()
                    left_nums.pop(i)
                    backtrack(left_nums,p_list)
        backtrack(nums,[])
        return res

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[MoonLee001]

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const vis = new Array(n).fill(false);
    let res = [];

    const backtrack = (path) => {
        if (path.length == n) {
            res.push(path.slice());
        }

        for (let i = 0; i < n; i++) {
            if (vis[i] || (i > 0 && nums[i - 1] == nums[i] && !vis[i - 1])) {
                continue;
            }
            path.push(nums[i]);
            vis[i] = true;
            backtrack(path);
            path.pop();
            vis[i] = false;
        }
    }
    backtrack([]);
    return res;
};

[L-SUI]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const ans = [];
    const vis = new Array(nums.length).fill(false);
    const backtrack = (idx, perm) => {
        if (idx === nums.length) {
            ans.push(perm.slice());
            return;
        }
        for (let i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.push(nums[i]);
            vis[i] = true;
            backtrack(idx + 1, perm);
            vis[i] = false;
            perm.pop();
        }
    }
    nums.sort((x, y) => x - y);
    backtrack(0, []);
    return ans;
};

[miss1]

思路

全排列，回溯，关键在于怎么去除重复项。先将数组nums排序，当遍历完一个数的所有情况，开始遍历下一个数时，判断这个数是否跟前一个数相等，若相等，则重复了，跳过

代码

var permuteUnique = function(nums) {
  let res = [];
  let list = [];
  nums.sort((a,b) => { return a - b; })
  const backTrack = function(result) {
    if (result.length === nums.length) {
      res.push([...result]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (list.includes(i)) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !list.includes(i - 1)) continue;
      result.push(nums[i]);
      list.push(i);
      backTrack(result);
      result.pop();
      list.pop();
    }
  };
  backTrack([]);
  return res;
};

复杂度

• time: O(n), n: 结果数组的长度
• space: O(n)

[hyh331]

Day82 思路

class Solution {
public:
    //记录 已经填过的数
    vector<int> vis;
    //回溯,四个参数，idx：下一个待填入的位置
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm){
        //idx==n说明当前小数组已经填满，将当前perm里的数全部压入ans
        if(idx == nums.size()){
            ans.push_back(perm);
            return ; 
        }

        for(int i=0; i<nums.size(); i++){
            //保证没有重复，vis[i]=1表示此数已经填过
            if(vis[i] || (i > 0 && nums[i] == nums[i-1] && !vis[i-1])){
                continue;
            }
            perm.push_back(nums[i]);
            vis[i]=1;
            backtrack(nums, ans, idx+1, perm);
            //回溯的时候要撤销该位置填的数以及标记，并继续尝试其他没被标记过的数。
            vis[i]=0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        //perm相当于ans里的小数组
        vector<int> perm;
        //为vis开辟空间
        vis.resize(nums.size());
        //对nums排序,保证相同的数字都相邻
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;

    }
};

复杂度分析

• 时间复杂度：O(n x n!) n为序列的长度
• 空间复杂度：O(n)

[tongyuhangg]

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        boolean[] isVisited = new boolean[nums.length];  

        // Special case
        if (nums.length == 0 || nums == null) { return res;}

        backTrack(list, res, nums, isVisited);
        return res;
    }

    private void backTrack(List<Integer> list, List<List<Integer>> res, int[] nums, boolean[] isVisited) {
        // Base case
        if (list.size() == nums.length) {
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if (list.size() > nums.length) {
            return;
        }

        // DFS
        for (int i=0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1] && !isVisited[i]) { continue;}
            if (isVisited[i]) { continue;}
            list.add(nums[i]);
            isVisited[i] = true;
            backTrack(list, res, nums, isVisited);
            list.remove(list.size()-1);
            isVisited[i] = false;
        }
    }
}

[Shuchunyu]

class Solution { boolean[] vis;

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    List<Integer> perm = new ArrayList<Integer>();
    vis = new boolean[nums.length];
    Arrays.sort(nums);
    backtrack(nums, ans, 0, perm);
    return ans;
}

public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
    if (idx == nums.length) {
        ans.add(new ArrayList<Integer>(perm));
        return;
    }
    for (int i = 0; i < nums.length; ++i) {
        if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
            continue;
        }
        perm.add(nums[i]);
        vis[i] = true;
        backtrack(nums, ans, idx + 1, perm);
        vis[i] = false;
        perm.remove(idx);
    }
}

}

[carterrr]

package redo.mistakescollection;

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.List;

public class 全排列II_47 { List<List> res = new ArrayList<>(); Deque dq = new ArrayDeque<>(); // 最后一位添加删除最方便 public List<List> permuteUnique(int[] nums) { Arrays.sort(nums); bt(nums, new boolean[nums.length]); return res; }

private void bt( int[] nums, boolean[] visited) { if(dq.size() == nums.length) { res.add(new ArrayList<>(dq)); return ; } for (int i = 0; i < nums.length; i++) { if(visited[i]) continue; // 因为是全排列 可以先选后面在选前面 所以必须要用visited数组 而且下一轮一定从0再开始 // !used[i - 1] 是因为 如果是本分支内第二个1 used[i - 1] = true 整体为false 不会跳过 因为 [1,1,2] 这种不可以剪掉 // 如果是第二个分支 已经有了 [1,1,2] // 现在用第二个1做第一个节点的时候 used[i - 1] 已经被上次for循环设为了 false 这种是需要跳过的 if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) { // 相同前面一个一定会处理的 continue; } visited[i] = true; dq.addLast(nums[i]); bt(nums, visited); dq.removeLast(); visited[i] = false; } } }

[zhishinaigai]

class Solution {
    vector<int> vis;

public:
    void backtrack(vector<int>& nums, vector<vector<int>>& ans, int idx, vector<int>& perm) {
        if (idx == nums.size()) {
            ans.emplace_back(perm);
            return;
        }
        for (int i = 0; i < (int)nums.size(); ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.emplace_back(nums[i]);
            vis[i] = 1;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = 0;
            perm.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> perm;
        vis.resize(nums.size());
        sort(nums.begin(), nums.end());
        backtrack(nums, ans, 0, perm);
        return ans;
    }
};

[LQyt2012]

思路

回溯

代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result = []
        path = []
        nums.sort()
        self.used = [0] * len(nums)
        self.backtrace(nums, path, 0)
        return self.result

    def backtrace(self, nums, path, depth):
        if depth == len(nums):
            self.result.append(path[:])
            return

        for i in range(len(nums)):
            if self.used[i] == 1:
                continue
            if i > 0 and nums[i] == nums[i-1] and self.used[i-1] == 0:
                continue

            self.used[i] = 1
            self.backtrace(nums, path+[nums[i]], depth+1)
            self.used[i] = 0

func permuteUnique(nums []int) [][]int {
    result := &[][]int{}
    path := []int{}
    used := make([]int, len(nums))
    sort.Ints(nums)
    backTrace(nums, path, used, result)
    return *result
}

func backTrace(nums, path, used []int, result *[][]int) {
    if len(path) == len(nums) {
        res := make([]int, len(path))
        copy(res, path)
        *result = append(*result, res)
        return
    }

    for i := 0;i<len(nums);i++ {
        if used[i] == 1 {
            continue
        }
        if i > 0 && nums[i] == nums[i-1] && used[i-1] == 0 {
            continue
        }
        used[i] = 1
        path = append(path, nums[i])
        backTrace(nums, path, used, result)
        path = path[:len(path)-1]
        used[i] = 0
    }
}

复杂度分析

时间复杂度：O(2^N*N)
空间复杂度：O(depth)

[ShuqianYang]

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        self.res = []
        check = [0 for i in range(len(nums))]

        self.backtrack([], nums, check)
        return self.res

    def backtrack(self, sol, nums, check):
        if len(sol) == len(nums):
            self.res.append(sol)
            return

        for i in range(len(nums)):
            if check[i] == 1:
                continue
            if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:
                continue
            check[i] = 1
            self.backtrack(sol+[nums[i]], nums, check)
            check[i] = 0

[xiayuhui231]

题目

全排列II

代码

class Solution {
    vector<vector<int>> ans;

public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        perm(nums, 0, nums.size() - 1);
        return ans;
    }

    void perm(vector<int> nums, int left, int right) {
        if (left == right)
            ans.push_back(nums);
        else {
            for (int i = left; i <= right; i++) {
                if (i != left && nums[left] == nums[i]) continue; 
                swap(nums[left], nums[i]);
                perm(nums, left + 1, right);
            }
        }
    }
};

[tensorstart]

var permuteUnique = function(nums) {
    if (nums == null)
        return;

    nums.sort((a, b) => a - b);
    const res = [];
    cal(nums, 0, res);
    return res; 
};
var swap = function(nums, i, j) {
    if (i === j)
        return;
    const t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
};

var cal = function (nums, first, result) {
    if (nums.length === first) {
        result.push([...nums]);
        return;
    }

    const map = new Map();
    for (let i = first; i < nums.length; i++) {
        if (!map.get(nums[i])) {
            map.set(nums[i], true);
            swap(nums, first, i);
            cal(nums, first + 1, result);
            swap(nums, first, i);
        }
    }
};

[TonyLee017]

思路

• 回溯法

  代码

  class Solution:
  def permuteUnique(self, nums: List[int]) -> List[List[int]]:
      nums.sort()
      self.res = []
      check = [0 for i in range(len(nums))]
  
      self.backtrack([], nums, check)
      return self.res
  
  def backtrack(self, sol, nums, check):
      if len(sol) == len(nums):
          self.res.append(sol)
          return
  
      for i in range(len(nums)):
          if check[i] == 1:
              continue
          if i > 0 and nums[i] == nums[i-1] and check[i-1] == 0:
              continue
          check[i] = 1
          self.backtrack(sol+[nums[i]], nums, check)
          check[i] = 0

  复杂度分析

• 时间复杂度：O(n*n!)
• 空间复杂度：O(n)

[freedom0123]

class Solution {
    List<List<Integer>> resource = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean []st = new boolean[10];
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        dfs(0,nums);
        return resource;
    }
    public void dfs(int u,int []nums){
        if(u==nums.length){
            resource.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++){           
            if(i>0 && nums[i] == nums[i-1] && !st[i-1]){
                continue;
            }
            if(!st[i]){
                path.add(nums[i]);
                st[i]=true;
                dfs(u+1,nums);
                st[i]= false;
                path.removeLast();
            }          
        }
    }
}

[linjunhe]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        def dfs(k):
            if k == n:
                res.append(nums[:])
                return
            s = set()
            for i in range(k, n):
                if nums[i] in s: continue
                if i!= k: nums[k], nums[i] = nums[i], nums[k]
                s.add(nums[k])
                dfs(k + 1)
                if i!= k: nums[k], nums[i] = nums[i], nums[k]
        dfs(0)
        return res

[XXjo]

代码

var permuteUnique = function(nums) {
    let res = [];
    let path = [];
    let isUsed = [];
    nums = nums.sort((a, b) => a - b);  //涉及重复元素，所以排序，为了方便后续剪枝去除重复值
    var backtrack = function(nums, path, isUsed){
        if(path.length === nums.length){
            res.push([...path]);
            return;
        }
        for(let i = 0; i < nums.length; i++){   //由于涉及全排列，所以每一层都要遍历所有元素
            if(isUsed[i]) continue;
            if(i > 0 && nums[i - 1] === nums[i] && isUsed[i - 1] === false) continue;
            path.push(nums[i]);
            isUsed[i] = true;
            backtrack(nums, path, isUsed);
            path.pop();
            isUsed[i] = false;
        }
    }

    backtrack(nums, path, isUsed);
    return res;
};

[xil324]

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums) == 0:
            return []; 
        self.res = []; 
        count = collections.Counter(nums); 
        self.traverse(nums, [], count); 
        return self.res

    def traverse(self, nums, path, count): 
        if len(path) == len(nums):
            self.res.append(path[:]); 
            return;
        for num in count: 
            if count[num] > 0:
                path.append(num); 
                count[num] -=1;
                self.traverse(nums,path, count);
                path.pop();
                count[num] += 1l

[Ellie-Wu05]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        results = []
        def backtrack(comb, counter):
            if len(comb) == len(nums):
                # make a deep copy of the resulting permutation,
                # since the permutation would be backtracked later.
                results.append(list(comb))
                return

            for num in counter:
                if counter[num] > 0:
                    # add this number into the current combination
                    comb.append(num)
                    counter[num] -= 1
                    # continue the exploration
                    backtrack(comb, counter)
                    # revert the choice for the next exploration
                    comb.pop()
                    counter[num] += 1

        backtrack([], Counter(nums))

        return results

[sallyrubyjade]

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
      var permuteUnique = function (nums) {
        if (nums.length === 1) {
          return [nums];
        }
        let res = [], map = {};
        nums.forEach((e, index) => {
          if (!map[e]) {
            map[e] = 1;
            let arr = [...nums];
            arr.splice(index, 1);
            permuteUnique(arr).forEach((e1) => {
              let arr = [e, ...e1];
              res.push(arr);
            });
          }
        });
        return res;
      };

[flaming-cl]

var permuteUnique = function(nums) {
  return new PermuteUnique(nums).permuteUnique();
};

class PermuteUnique {
  constructor(nums) {
    this.nums = nums.sort((a, b) => a - b);
    this.used = {};
    this.set = [];
    this.ans = [];
  }

  permuteUnique() {
    this.permuteUniqueRecur(0);
    return this.ans;
  }

  permuteUniqueRecur(index) {
    if (index === this.nums.length) {
      this.ans.push([...this.set]);
      return;
    }

    for (let i = 0; i < this.nums.length; i++) {
      if (this.used[i] || i > 0 && !this.used[i - 1]  && this.nums[i] === this.nums[i - 1]) {
        continue;
      }
      this.set.push(this.nums[i]);
      this.used[i] = true;
      this.permuteUniqueRecur(index + 1);
      this.used[i] = false;
      this.set.pop();
    }
  }
}

[revisegoal]

回溯

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        backtrack(ans, new ArrayList<Integer>(),
                  nums, new boolean[nums.length]);
        return ans;
    }

    void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, boolean[] used) {       
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                tempList.add(nums[i]);
                used[i] = true;
                backtrack(list, tempList, nums, used);
                tempList.remove(tempList.size() - 1);
                used[i] = false;
            }
        }

        if (tempList.size() == nums.length && !list.contains(tempList)) {
            list.add(new ArrayList<>(tempList));
        }
    }
}

• time: O(2 * n ^ 2)
• space: O(n)

[flyzenr]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # res用来存放结果
        if not nums: return []
        res = []
        used = [0] * len(nums)
        def backtracking(nums, used, path):
            # 终止条件
            if len(path) == len(nums):
                res.append(path.copy())
                return
            for i in range(len(nums)):
                if not used[i]:
                    if i>0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    used[i] = 1
                    path.append(nums[i])
                    backtracking(nums, used, path)
                    path.pop()
                    used[i] = 0
        # 记得给nums排序
        backtracking(sorted(nums),used,[])
        return res

[Yongxi-Zhou]

思路

backtracking, 通过visited数组排除重复的结果

代码

    class Solution:
        def permuteUnique(self, nums: List[int]) -> List[List[int]]:
            res = []
            n = len(nums)
            visited = [False] * n
            nums.sort()
            self.backtracking(nums, visited, res, n, [])
            return res

        def backtracking(self, nums, visited, res, length, temp):
            if len(temp) == length:
                res.append(temp[:])
                return

            for i in range(length):
                if i > 0 and visited[i] == False and visited[i - 1] == True and nums[i] == nums[i - 1]:
                    continue
                if not visited[i]:
                    temp.append(nums[i])
                    visited[i] = True
                    self.backtracking(nums, visited, res, length, temp)
                    temp.pop()
                    visited[i] = False

复杂度

time O(N!) space O(N)