【Day 82 】2021-11-30 - 47 全排列 II #101

azl397985856 · 2021-11-29T15:12:20Z

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

回溯
数组
剪枝

题目描述

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

示例:

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

The text was updated successfully, but these errors were encountered:

yanglr · 2021-11-29T15:45:01Z

思路:

方法: 回溯

不需要排序, 只需要使用set 去重

代码:

实现语言: C++

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.empty()) return {{}};
        if (nums.size() == 1) return {nums};
        vector<vector<int>> result;
        dfs(nums, result, 0);      // dfs: 开始回溯, 一开始要处理的区间是[0, len-1]
        return result;
    }
private:
    /* 每次去处理子区间 [startPos, len - 1], startPos表示将要处理的剩下数中第一个数的index */
    void dfs(vector<int> nums, vector<vector<int>>& result, int startPos) {   
        if (startPos == nums.size() - 1) {  /* 已经排列到len 位置，超出了数组范围，这意味着此时已经完成了排列 */
            result.push_back(nums); 
            return;
        }

        unordered_set<int> usedDict;  /* 记录哪些数已经用过 */
        for (int i = startPos; i < nums.size(); ++i) { /* startPos 是当前正在选择的位, i 是startPos位置将要选择的数的当前位置 */
            swap(nums[i], nums[startPos]);   /* Choose: 将第i位数字交换到startPos位置, 完成startPos位置的选择 */
            // 仅当"当前数"没被使用过时才可以递归调用
            if (!usedDict.count(nums[startPos])) {
                usedDict.insert(nums[startPos]);
                dfs(nums, result, startPos + 1);  /* Explore using dfs: 递归的向前推进1步(1个格子), 选择下一位数字  */
            }
            swap(nums[i], nums[startPos]);   /* Un-choose: 重置为选择之前的状态，重新选择下一位数字  */
        }
    }
};

复杂度分析:

时间复杂度：O(n×n!)，其中 n 为序列的长度。
空间复杂度：O(n)。

laurallalala · 2021-11-29T16:22:07Z

代码

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        visited = set()
        self.helper(nums, res, [], visited)
        return res
    
    def helper(self, nums, res, cur, visited):
        if len(nums) == 0:
            s = ''.join([str(item) for item in cur])
            if s not in visited:
                res.append(cur)
                visited.add(s)
        i = 0
        while i <len(nums):
            curNum = nums[i]
            j = i+1
            while j<len(nums):
                if nums[j] == curNum:
                    j += 1
                else:
                    break
            self.helper(nums[:i]+nums[i+1:], res, cur+[curNum], visited)
            i = j

revisegoal · 2021-11-29T16:27:12Z

Note

回溯，剪枝

Code

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));
        }
    }
}

Complexity

time：O(n^2)
space：O(n^2)

for123s · 2021-11-29T16:52:53Z

代码

语言支持：C++

C++ Code:

class Solution {
public:
    vector<vector<int>> res;
    
    void dfs(vector<int> nums, int l, int r)
    {
        if(l==r)
        {
            res.push_back(nums);
            return;
        }
        for(int i=l;i<=r;i++)
        {
            if(i!=l&&nums[l]==nums[i])
                continue;
            swap(nums[i],nums[l]);
            dfs(nums,l+1,r);
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        dfs(nums,0,nums.size()-1);
        return res;
    }
};

mixtureve · 2021-11-29T17:23:42Z

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return ret;
        }
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backtrack(ret, nums, visited, new ArrayList<>(), 0); // 注意 因为这个是在原数组上交换，所以我们不需要 有一个 cur list
        return ret;
    }
    
    private void backtrack(List<List<Integer>> ret, int[] nums, boolean[] visited, List<Integer> cur, int level) {
        // base case
        if (level == nums.length) {
            ret.add(new ArrayList<>(cur));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // 保证在填第 level 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

            if (visited[i] || (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            cur.add(nums[i]);
            backtrack(ret, nums, visited, cur, level + 1);
            cur.remove(level);
            visited[i] = false;
        }
    } 
}

biancaone · 2021-11-29T17:58:29Z

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return []
        
        nums.sort()
        result = []
        visited = [False for _ in range(len(nums))]
        self.dfs(nums, visited, [], result)
        return result
    
    
    def dfs(self, nums, visited, path, result):
        if len(path) == len(nums):
            result.append(list(path))
            return
        
        for i in range(len(nums)):
            if visited[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:
                continue
            visited[i] = True
            path.append(nums[i])
            self.dfs(nums, visited, path, result)
            visited[i] = False
            path.pop()

ai2095 · 2021-11-29T19:19:01Z

47. Permutations II

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

Topics

-Backtracking

思路

Backtracking

代码 Python

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(res, visited):
            nonlocal result, nums_len
            if len(res) == nums_len:
                result.append(res[:])
                return
              
            for i in range(nums_len):
                if i > 0 and i - 1 in visited and nums[i-1] == nums[i]:
                    continue
                if i in visited:
                    continue
                visited.add(i)
                res.append(nums[i])
                backtrack(res, visited)
                res.pop()
                visited.remove(i)
                
        
        
        result = []
        nums.sort()
        nums_len = len(nums)     
        backtrack([], set())

        return result

复杂度分析

k is the # of duplicate elements.
时间复杂度： O(N(N-1)...(N-k+1))

空间复杂度： O(N)

ZacheryCao · 2021-11-29T19:21:59Z

Idea

Backtracking

Code

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(cur):
            if len(cur) == len(nums):
                ans.add(tuple(cur))
                return
            for i in range(len(nums)):
                if nums[i] != math.inf:
                    cur.append(nums[i])
                    nums[i] = math.inf
                    dfs(cur)
                    nums[i] = cur.pop()
            
        
        ans = set()
        dfs([])
        return ans

Complexity:

Time: O(N X N!)
Space: O(N)

CoreJa · 2021-11-29T19:40:26Z

思路

经典回溯题，个人感觉比昨天要简单些，全排列的话重点在于取了一个数之后，还可以取之前的数，所以dfs的时候要把除了取的数以外的数作为参数带入。

这里不得不说切片是真的好用，省了好多事情，每次传入nums[:i] + nums[i + 1:]就行了。别的语言可能会麻烦一点，比如用标记表示哪些数字已经被取用等

此外考虑到输入可能有重复数字，需要和昨天类似的去重，要么就将nums排序然后确保nums[i]!=nums[i-1]，要么维护一个set来保证每次加进去的数字不重复，重复就continue

代码

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

        def dfs(nums, cur_ans):
            visited = set()
            if not nums:
                ans.append(cur_ans)
                return
            for i, num in enumerate(nums):
                if num in visited:
                    continue
                visited.add(num)
                dfs(nums[:i] + nums[i + 1:], cur_ans + [num])

        dfs(nums, [])
        return ans

yingliucreates · 2021-11-29T19:42:17Z

const permuteUnique = function(nums) {
const res = [];
const length = nums.length;
const visited = new Array(length).fill(0);
const memo = new Set();
traverse(nums, res, [], length, visited, memo);
return res;
};

const traverse = (nums, res, temp, length, visited, memo) => {
if (temp.length === length) {
res.push([...temp]);
return;

}

for (let i = 0; i < length; i++) {
    if (visited[i]) continue;
    visited[i] = 1;
    temp.push(nums[i]);
    if (memo.has(temp.join(''))) {
        temp.pop();
        visited[i] = 0;
        continue;
    }
    memo.add(temp.join(''));
    traverse(nums, res, temp, length, visited, memo);
    temp.pop();
    visited[i] = 0;
}

}

Laurence-try · 2021-11-29T21:00:58Z

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

JiangyanLiNEU · 2021-11-29T21:04:27Z

var permuteUnique = function(nums) {
    let result = new Set();
    let final=[];
    var combine = (cur, rest) => {
        if (rest.length == 0){
            if (!result.has(JSON.stringify(cur))){
                result.add(JSON.stringify(cur));
                final.push([...cur])
            }
        }else{
            for (let i=0; i<rest.length; i++){
                const newRest = rest.filter((item, index) => index!=i);
                combine([...cur, rest[i]], newRest)
            }
        }
    };
    combine([], nums);
    return final;
};

class Solution(object):
    def permuteUnique(self, nums):
        result = set()
        def combine(cur, rest):
            if rest == []:
                result.add(tuple(cur))
            else:
                for i in range(len(rest)):
                    choose = rest[i]
                    rest1 = deepcopy(rest)
                    rest1.pop(i)
                    cur.append(choose)
                    combine(cur, rest1)
                    cur.pop()
        combine([], nums)
        return [list(item) for item in result]

skinnyh · 2021-11-29T21:32:57Z

Note

Use a visited set instead of using current position to avoid duplicate results because the order of numbers matters in permutation.
To avoid the duplicate permutation due to the same numbers, sort the nums and add a duplicate number into permutation only if the pervious duplicate has been visited.

Solution

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def backtrack(path, visited):
            if len(path) == len(nums):
                res.append(path.copy())
                return
            for i in range(len(nums)):
                if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
                    continue
                path.append(nums[i])
                visited[i] = True
                backtrack(path, visited)
                visited[i] = False
                path.pop()
        res = []
        nums.sort()
        backtrack([], [False] * len(nums))
        return res

Time complexity: O(N!)

Space complexity: O(N)

pan-qin · 2021-11-29T22:22:37Z

Idea:

backtracking. Use a hashmap to store the available amount of each number.

Complexity:

Time: N!*N.
Space: O(n)

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        HashMap<Integer,Integer> counter = new HashMap<>();
        for(int n:nums) {
            counter.put(n,counter.getOrDefault(n,0)+1);
        }
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> perm = new LinkedList<>();
        helper(nums,res,perm,counter);
        return res;
    }
    private void helper(int[] nums, List<List<Integer>> res, LinkedList<Integer> perm,HashMap<Integer,Integer> counter) {
        if(perm.size()==nums.length) {
            res.add(new LinkedList<>(perm));
            return;
        }
        for(Map.Entry<Integer,Integer> entry: counter.entrySet()) {
            int num = entry.getKey();
            Integer count = entry.getValue();
            if(count ==0)
                continue;
            perm.add(num);
            counter.put(num,--count);
            helper(nums,res,perm,counter);
            int last=perm.removeLast();
            counter.put(last,counter.get(last)+1);
        }
    }
}

laofuWF · 2021-11-29T22:31:10Z

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        seen = [False for i in range(len(nums))]
        nums.sort()
        self.backtrack(res, nums, seen, [])
        return res
    
    def backtrack(self, res, nums, seen, curr_list):
        if len(curr_list) == len(nums):
            res.append(curr_list.copy())
            return
        
        for i in range(len(nums)):
            # avoid repeat pick of same element that's picked before
            if seen[i]: continue
            if i > 0 and nums[i] == nums[i - 1] and not seen[i - 1]: continue
            
            seen[i] = True
            curr_list.append(nums[i])
            self.backtrack(res, nums, seen, curr_list)
            seen[i] = False
            curr_list.pop()

Daniel-Zheng · 2021-11-29T23:50:15Z

思路

回溯。

代码(C++)

class Solution {
public:
    vector<int> path;
    vector<vector<int>> res;
    void backtracking(vector<int>& nums, vector<bool>& visited) {
        if (path.size() == nums.size()) res.push_back(path);
        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            if (visited[i]) continue;
            visited[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, visited);
            visited[i] = false;
            path.pop_back();
        }
    }
    
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> visited(nums.size(), false);
        sort(nums.begin(), nums.end());
        backtracking(nums, visited);
        return res;
    }
};

复杂度分析

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

zhangzz2015 · 2021-11-29T23:51:44Z

思路

找全部的排列，采用回溯递归方法，画出递归树，树的高度为 n ，数的宽度也为n，但是因为前面选择后的num，后面不能选择，因此需要利用visit flag，表明是否前面选择过。另外还有重复问题，首先进行排序，重复需要去除的是开一个新的分支，并且不是第一次选择。因此利用visit flag ，以及当前数和前面一个数是否相同进行减枝。时间复杂度为O(n^n)，空间复杂度为O(n)。另外还有进一步优化方法，通过swap实现，

关键点

代码

语言支持：C++

C++ Code:

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        
        sort(nums.begin(), nums.end()); 
        
        vector<int> onePath; 
        vector<vector<int>> ret; 
        vector<bool> visit(nums.size(), false); 
        backTrac(nums, onePath, ret, visit); 
        
        return ret; 
        
    }
    
    
    void backTrac(vector<int>& nums, vector<int>& onePath, vector<vector<int>>& ret, vector<bool>& visit)
    {
        
        if(onePath.size() == nums.size()) // return results. 
        {
            
            ret.push_back(onePath);
            return ; 
                
        }
                
        for(int i=0; i< nums.size(); i++)
        {
            if(visit[i]==true )
                continue; 
            if(i>0 && nums[i] == nums[i-1] && visit[i-1] == false) 
                continue; 
            
            visit[i] = true; 
            onePath.push_back(nums[i]); 
            
            backTrac(nums, onePath, ret, visit); 
            
            visit[i] = false; 
            onePath.pop_back();             
        }
        
    }
};

kidexp · 2021-11-30T00:48:52Z

thoughts

回溯+set来记录下标来查询某个数是不是访问过了

code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        visited_nums = set()
        results = []
        single_solution = []

        def dfs():
            if len(single_solution) == len(nums):
                results.append(list(single_solution))
                return
            for num in nums:
                if num not in visited_nums:
                    visited_nums.add(num)
                    single_solution.append(num)
                    dfs()
                    single_solution.pop()
                    visited_nums.remove(num)

        dfs()
        return results

complexity

Time O(n!)
Space O(n!)

shawncvv · 2021-11-30T00:49:59Z

思路

回溯

代码

JavaScript Code

function backtrack(list, nums, tempList, visited) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    if (visited[i]) continue;
    // visited[i - 1] 容易忽略
    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue;

    visited[i] = true;
    tempList.push(nums[i]);
    backtrack(list, nums, tempList, visited);
    visited[i] = false;
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const list = [];
  backtrack(
    list,
    nums.sort((a, b) => a - b),
    [],
    []
  );
  return list;
};

复杂度

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

tongxw · 2021-11-30T01:31:06Z

思路

回溯，剪枝的前提是先排序，然后遍历同一层时，如果数字已经出现过，就剪枝。

代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        boolean[] selected = new boolean[n];
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, ans, path, selected);
        return ans;
    }
    
    private void dfs(int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] selected) {
        int n = nums.length;
        if (path.size() == n) {
            ans.add(new ArrayList<>(path));
            return;
        }
        
        for (int i=0; i<n; i++) {
            if (selected[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i-1] && selected[i-1]) {
                continue;
            }
            
            path.add(nums[i]);
            selected[i] = true;
            dfs(nums, ans, path, selected);
            path.remove(path.size() - 1);
            selected[i] = false;
        }
    }
}

TC: O(n!)
SC: O(n!)

chun1hao · 2021-11-30T01:49:23Z

var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b);
  let ans = [];
  let len = nums.length;
  let visit = new Array(len).fill(false);
  let backtrack = (pre, visit) => {
    if (pre.length === len) {
      return ans.push(pre.slice());
    }
    for (let i = 0; i < len; i++) {
      if (i > 0 && nums[i] === nums[i - 1] && !visit[i - 1]) continue;
      if (!visit[i]) {
        visit[i] = true;
        pre.push(nums[i]);
        backtrack(pre, visit);
        visit[i] = false;
        pre.pop();
      }
    }
  };
  backtrack([], visit);
  return ans;
};

wenlong201807 · 2021-11-30T01:57:15Z

代码块

var permuteUnique = function (nums) {
  nums.sort((a, b) => {
    return a - b;
  });
  let result = [];
  let path = [];

  function backtracing(used) {
    if (path.length === nums.length) {
      result.push(path.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue;
      }
      if (!used[i]) {
        used[i] = true;
        path.push(nums[i]);
        backtracing(used);
        path.pop();
        used[i] = false;
      }
    }
  }
  backtracing([]);
  return result;
};

时间复杂度和空间复杂度

时间复杂度 O(n)
空间复杂度 O(1)

yan0327 · 2021-11-30T02:01:35Z

func permuteUnique(nums []int) [][]int {
    sort.Ints(nums)
    hash := make([]bool,len(nums))
    out := [][]int{}
    var dfs func(path []int,nums []int)
    dfs = func(path []int,nums []int){
        if len(path) == len(nums){
            temp := make([]int,len(path))
            copy(temp,path)
            out = append(out,temp)
            return
        }
        for i:=0;i<len(nums);i++{
            if hash[i] == true{
                continue
            }
            if i>=1&&nums[i] == nums[i-1]&&hash[i-1]{
                continue
            }
            path = append(path,nums[i])
            hash[i] = true
            dfs(path,nums)
            hash[i] = false
            path = path[:len(path)-1]

        }
    }
    dfs([]int{},nums)
    return out
}

时间复杂度O（n*n!）
空间复杂度O（n）

GZ712D · 2021-11-30T02:04:58Z

代码

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));
    }
}

}

QiZhongdd · 2021-11-30T02:17:26Z


function backtrack(list, nums, tempList, visited) {
  if (tempList.length === nums.length) return list.push([...tempList]);
  for (let i = 0; i < nums.length; i++) {
    if (visited[i]) continue;
    // visited[i - 1] 容易忽略
    if (i > 0 && nums[i] === nums[i - 1] && visited[i - 1]) continue;

    visited[i] = true;
    tempList.push(nums[i]);
    backtrack(list, nums, tempList, visited);
    visited[i] = false;
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function (nums) {
  const list = [];
  backtrack(
    list,
    nums.sort((a, b) => a - b),
    [],
    []
  );
  return list;
};

joeytor · 2021-11-30T02:19:24Z

思路

使用回溯的方法

先对 nums 进行排序, 方便后面剪枝

每次递归的 base case 是 len(cur) == len(nums), 代表了已经用了所有数字, 那么将这个 cur 的 copy 加入 res 数组中

否则遍历所有可能都数字

剪枝条件是如果 i > 0 并且 nums[i] == nums[i-1] 并且 nums[i-1] 没有被使用过, 那么优先使用第一个相同 value 的数字, 所以跳过

如果 i 不在 used 中, 没有使用过, 那么进行回溯

在 used 中加入 i, 在 cur 中加入 nums[i], 并且进行回溯, 完成之后撤销两个操作

最后返回 res 数组

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:

        res = []
        used = set()
        nums.sort()

        def dfs(cur):
            if len(cur) == len(nums):
                res.append(cur[:])
                return
            
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1] and (i-1) not in used:
                    continue
                if i not in used:
                    used.add(i)
                    cur.append(nums[i])
                    dfs(cur)
                    used.remove(i)
                    cur.pop()
        
        dfs([])
        return res

复杂度

时间复杂度: O(n * n!) 回溯被调用 O(n!) 次, 每次需要 O(n) 的时间复制答案

空间复杂度: O(n) O(n) 的 used set 标记数组, 递归栈的深度也是 O(n)

pophy · 2021-11-30T02:26:08Z

思路

backtracking
排序去重
需要用额外数组记录当前数是否已经被用过

Java Code

class Solution {    
    List<List<Integer>> res;
    boolean[] visited;
    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList();
        visited = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(nums, new ArrayList());
        return res;
    }
    
    private void dfs (int[] nums, List<Integer> path) {
        if (path.size() == nums.length) {
            res.add(new ArrayList(path));
        }
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && visited[i-1] && nums[i] == nums[i - 1]) {
                continue;
            }
            if (visited[i]) {
                continue;
            }
            path.add(nums[i]);
            visited[i] = true;
            dfs(nums, path);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}

guangsizhongbin · 2021-11-30T12:18:21Z

func permuteUnique(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    // 当前排列的数组
    perm := []int{}
    // 标记，已经用过的元素
    vis := make([]bool, n)
    var backtrack func(int)

    // idx 当前遍历的位置
    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]
        }
    }

    // 从0的位置开始
    backtrack(0)
    return

}

ymkymk · 2021-11-30T12:19:41Z

思路

回溯算法

代码

``


class Solution {

     boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        // 对nums进行排序
        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);
        }
    }
}

复杂度分析

时间复杂度：O(n×n!)，其中 n 为序列的长度

空间复杂度：O(n)

carterrr · 2021-11-30T12:34:21Z

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

private void dfs(List<List<Integer>> res, Deque<Integer> branch, int[] nums, boolean[] used) {
    if(branch.size() == nums.length) {
        res.add(new ArrayList<>(branch));
    }
    
    for(int i = 0; i< nums.length; i++) {
        if(used[i]) {
            continue;
        }
        // && nums[i] == nums[i - 1]  如  [1,1,2]第一个1的时候 为false   
        // !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] && !used[i - 1]) {
            continue;
        }
        branch.addLast(nums[i]);
        used[i] = true;
        dfs(res, branch, nums, used);
        used[i] = false;
        branch.removeLast();
    }
}

}

HouHao1998 · 2021-11-30T12:34:41Z

代码

class Solution {
	private List<List<Integer>> res = new ArrayList<>();
	/** 用于去除排列后的重复项 */
	private Set<String> set = new HashSet<>();

	public List<List<Integer>> permuteUnique(int[] nums) {
		// 回溯
		backtrack(nums, new ArrayList<>());
		return res;
	}

	/**
	 * 回溯
	 *
	 * @param nums 待全排列的数组
	 * @param idxList 索引列表：用于判断当前元素是否已经排列过
	 */
	private void backtrack(int[] nums, List<Integer> idxList) {
		// 如果所有元素都排列过，处理结果
		if (idxList.size() == nums.length) {
			List<Integer> list = new ArrayList<>();
			// 通过索引list，构建元素list
			for (int index : idxList) {
				list.add(nums[index]);
			}
			// 因为数组中含有重复元素，所以全排列后可能会有重复，需要去重
			if (!set.contains(list.toString())) {
				set.add(list.toString());
				res.add(list);
			}
			return;
		}
		for (int i = 0; i < nums.length; i++) {
			// 如果nums[i]已经排序过，则跳过
			if (idxList.contains(i)) {
				continue;
			}
			idxList.add(i);
			backtrack(nums, idxList);
			idxList.remove(idxList.size() - 1);
		}
	}
}

复杂度

时间复杂度：O(n×n!)，其中 n 为序列的长度
空间复杂度：O(n)

hellowxwworld · 2021-11-30T13:02:17Z

void backtrace(int start, vector<int>& nums, vector<bool>& visited, vector<int>& curArray, vector<vector<int>>& res) {
    if (start >= nums.size()) {
        if (start == nums.size())
            res.push_back(curArray);
        return ;
    }
    for (int i = 0; i < nums.size(); ++i) {
        if (visited[i])
            continue;
        if (i - 1 >= 0 && nums[i] == nums[i - 1] && !visited[i - 1])
            return ;
        visited[i] = true;
        curArray.push_back(nums[i]);
        backtrace(start + 1, nums, visited, curArray, res);
        curArray.pop_back();
        visited[i] = false;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> curArray;
    vector<bool> visited(nums.size(), false);
    sort(nums.begin(), nums.end());
    backtrace(0, nums, visited, curArray, res);
    return res;
}

HWFrankFung · 2021-11-30T13:05:00Z

Codes

var permuteUnique = function(nums) {
    let n = nums.length;
    nums = nums.sort((a,b) => {return a - b});
    let res = [];
    let tmpPath = [];
    let hash = {};
    let backtrack = (tmpPath) => {
        if(tmpPath.length == n){
            res.push(tmpPath);
            return;
        }
        for(let i = 0;i < n;i++){
            if(hash[i] || (i > 0 && !hash[i-1] && nums[i-1] == nums[i])) continue;
            hash[i] = true;
            tmpPath.push(nums[i]);
            backtrack(tmpPath.slice());
            hash[i] = false;
            tmpPath.pop();
        }
    }
    backtrack(tmpPath);
    return res;
};

asaoba · 2021-11-30T13:44:54Z

class Solution {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    List<Integer> ls=new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0) return res;
        boolean[] used=new boolean[nums.length];
        for(boolean u:used){
            u=false;
        }
        Arrays.sort(nums);
        backTracking(nums,used);
        return res;

    }
    public void backTracking(int[] nums,boolean[] used){
        if(ls.size()==nums.length){
            res.add(new ArrayList(ls));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
            if(used[i]==true) continue;
            used[i]=true;
            ls.add(nums[i]);
            backTracking(nums,used);
            ls.remove(ls.size()-1);
            used[i]=false;
        }
    }
}

thinkfurther · 2021-11-30T13:46:59Z

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.result = []
        self.backtrack(nums, [])
        return self.result
    
    def backtrack(self,numbers, pre):
        if len(numbers) <= 1:
            self.result.append(pre + numbers)
            return
        for key, value in enumerate(numbers):
            if value not in numbers[:key]:
                self.backtrack(numbers[:key] + numbers[key + 1:], pre+[value])

ccslience · 2021-11-30T13:48:31Z

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        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

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

L-SUI · 2021-11-30T13:51:53Z

/**

@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;
};

joriscai · 2021-11-30T13:54:56Z

思路

递归回溯
元素不可重复，重复使用的剪枝

代码

javascript

/*
 * @lc app=leetcode.cn id=47 lang=javascript
 *
 * [47] 全排列 II
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
  // 先排序，便于去重
  nums.sort((a, b) => a - b)
  const result = []
  const path = []

  function backtracing(used) {
    // 长度一致，说明已经完成排列了
    if (path.length === nums.length) {
      result.push(path.slice())
      return
    }
    for (let i = 0; i < nums.length; i++) {
      // 当前元素已经使用
      if (used[i]) {
        continue
      }
      // 判断当前元素是否与上一个元素相同，且上个元素是否使用，避免重复
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
        continue
      }

      used[i] = true
      path.push(nums[i])
      backtracing(used)
      path.pop()
      used[i] = false
    }
  }
  backtracing([])
  return result
};
// @lc code=end

复杂度分析

时间复杂度：O(2^n)，先排序，要nlogn。回溯查找时，横向有n个选择，在回溯时，执行次数为n^2，即为n * n^2。
空间复杂度：O(n)，除答案数组外，空间复杂度取决于递归的栈深度，还有标记数组。栈为n，标记数组为n，即2n。O(n)

carinSkyrim · 2021-11-30T14:10:26Z

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

asterqian · 2021-11-30T14:24:01Z

思路

需要用一个visited数组来记录，以防漏掉可能解

代码

class Solution {
public:
    void backtrack(vector<vector<int>>& res, vector<int>& n, vector<int>& nums,
                   vector<bool>& vis) {
        if (n.size() == nums.size()) {
            res.push_back(n);
            return;
        }
        for (int i = 0; i < nums.size(); ++i) {
            // 去重：排序之后，如果现在这个数字和前一个相同，并且前一个已经visit过了的话就跳过
            // 例子：11, 我们会有1a1b两种情况，那只要限定必须先放1a再放1b就可以去重，所以如果1a（前一个）没有被visit的话就continue
            if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) continue;
            if (!vis[i]) {
                vis[i] = true;
                n.push_back(nums[i]);
                backtrack(res, n, nums, vis);
                vis[i] = false;
                n.pop_back();
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        vector<int> n;
        vector<bool> vis(nums.size());
        backtrack(res, n, nums, vis);
        return res;
    }
};

时间复杂度 O(N!*op(res))

空间复杂度 O(N*N!)

mokrs · 2021-11-30T14:30:34Z

class Solution {
private:
	vector<int> visit;

	void backtrack(vector<int>& nums, vector<vector<int>>& res, int idx, vector<int>& perm) {
		if (idx == nums.size()) {
			res.emplace_back(perm);
			return;
		}

		for (int i = 0; i < nums.size(); ++i) {
			if (visit[i] || (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1])) {
				continue;
			}

			perm.emplace_back(nums[i]);
			visit[i] = 1;

			backtrack(nums, res, idx + 1, perm);
			visit[i] = 0;

			perm.pop_back();
		}
	}
    
public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		visit.resize(nums.size());

		vector<vector<int>> res;
		sort(nums.begin(), nums.end());

		vector<int> perm;		
		backtrack(nums, res, 0, perm);

		return res;
	}
};

naivecoder-irl · 2021-11-30T14:30:34Z

class Solution {
    List<List<Integer>> res=new ArrayList<List<Integer>>();
    List<Integer> ls=new ArrayList<Integer>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums.length==0) return res;
        boolean[] used=new boolean[nums.length];
        for(boolean u:used){
            u=false;
        }
        Arrays.sort(nums);
        backTracking(nums,used);
        return res;

    }
    public void backTracking(int[] nums,boolean[] used){
        if(ls.size()==nums.length){
            res.add(new ArrayList(ls));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
            if(used[i]==true) continue;
            used[i]=true;
            ls.add(nums[i]);
            backTracking(nums,used);
            ls.remove(ls.size()-1);
            used[i]=false;
        }
    }
}

vincentLW · 2021-11-30T14:35:32Z


var permuteUnique = function (nums) {
  if (!nums.length) return [];
  const res = [];

  nums.sort((a, b) => a - b);
  function recur(arr, usedIndex) {
    if (arr.length === nums.length) {
      res.push(arr);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (usedIndex.includes(i)) {
        continue;
      }

      if (i > 0 && nums[i - 1] === nums[i] && usedIndex.includes(i)) {
        continue;
      }

      recur([...arr, nums[i]], [...usedIndex, i]);
    }
  }

  recur([], []);
  return res;
};

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

chenming-cao · 2021-11-30T14:45:54Z

解题思路

回溯+剪枝。参考官方题解。因为我们要求排列，在排列中，每个元素只出现一次，所以我们使用一个visited数组来记录每个元素的被访问情况。去重和组合总和II的方法类似。先将数组排序，然后当遇到当前元素和之前一个元素相等并且前一个元素已经被访问过时，我们跳过当前元素。

代码

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

    private void backtrack(int[] nums, List<Integer> list, List<List<Integer>> result, boolean[] visited) {
        // if the length of list is equal to the length of nums, we find one permutation
        if (list.size() == nums.length) {
            result.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // when the current element is equal to previous element and previous element is visited
            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1]) {
                continue;
            }
            // in permutation, one element will only show up once, if this element is visited, we will skip it
            // if this element is not visited, continue backtracking to add another element
            if (!visited[i]) {
                visited[i] = true;
                list.add(nums[i]);
                backtrack(nums, list, result, visited);
                visited[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

复杂度分析

时间复杂度：O(n! * op(res))，n为数组长度
空间复杂度：O(n * n!)

ysy0707 · 2021-11-30T14:51:55Z

思路：回溯+剪枝

class Solution {
    //res 设为全局变量，则不需要被当做参数传入了
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        int n =nums.length;
        List<Integer> tmp = new ArrayList<>();
        //全排列同一个数字不可出现 2 次
        //所以需创建一个额外数组跟踪每一个数字的使用情况, 其初始为全 0。
        int[] visited = new int[n];
        Arrays.sort(nums);

        backtrack(nums, tmp, visited);
        return res;
    }
    public void backtrack(int[] nums, List<Integer> tmp, int[] visited){
        if(tmp.size() == nums.length){
            res.add(new ArrayList<>(tmp));
            return;
        }
        for(int i = 0; i <nums.length; i++){
            if(visited[i] == 1){
                continue;
            }
            //剪枝条件：在搜索之前就对 nums 数组排序（为了让相同的元素在一起），
            //如果本次搜索的起点和上一次的搜索起点相同，即 nums[i]==nums[i−1]，
            //并且 nums[i-1]的状态为未使用
            //此时 nums[i] 的搜索结果一定与 nums[i−1] 的搜索结果相同，
            //肯定会发生重复，所以需要进行剪枝（直接跳过即可）。
            if(i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0){
                continue;
            }
            //操作
            visited[i] = 1;
            tmp.add(nums[i]);

            backtrack(nums, tmp, visited);
            //撤回
            visited[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

时间复杂度：O(NN!)
空间复杂度：O(NN!)

ChenJingjing85 · 2021-11-30T14:52:29Z

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        visits = [0 for _ in range(n)]
        path = []
        nums.sort()
        def backtrack(first):
            if first == n:
                res.append(path[:])
            for i in range(n):
                if i > 0 and nums[i] == nums[i-1] and visits[i-1]==1:
                    continue
                if visits[i] == 1:
                    continue
                path.append(nums[i])
                visits[i] = 1
                backtrack(first+1)
                visits[i] = 0
                path.pop()              

        backtrack(0)
        return res

时间复杂度 O（N！）
空间复杂度 O（N！）

BreezePython · 2021-11-30T15:16:51Z

思路

深度优先搜索

代码

class Solution:
    def permuteUnique(self, nums):
        ret = []
        nums.sort()
        stage = [0 for _ in nums]
        path = []

        def dfs(li):
            if len(li) == len(path):
                ret.append(path[:])
                return

            for i in range(len(li)):
                if stage[i] == 1:
                    continue
                if i > 0 and li[i] == li[i - 1] and stage[i - 1] == 0:
                    continue
                path.append(li[i])
                stage[i] = 1
                dfs(li)
                path.pop()
                stage[i] = 0

        dfs(nums)
        return ret

复杂度

时间复杂度：O(2^n)
空间复杂度：O(n)

brainlds · 2021-11-30T15:31:21Z

class Solution {
List<List> res=new ArrayList<List>();
List ls=new ArrayList();
public List<List> permuteUnique(int[] nums) {
if(nums.length==0) return res;
boolean[] used=new boolean[nums.length];
for(boolean u:used){
u=false;
}
Arrays.sort(nums);
backTracking(nums,used);
return res;

}
public void backTracking(int[] nums,boolean[] used){
    if(ls.size()==nums.length){
        res.add(new ArrayList(ls));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(i>0 && nums[i]==nums[i-1] && used[i-1]==false) continue;
        if(used[i]==true) continue;
        used[i]=true;
        ls.add(nums[i]);
        backTracking(nums,used);
        ls.remove(ls.size()-1);
        used[i]=false;
    }
}

}

Yufanzh · 2021-11-30T15:35:58Z

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(counter, path):
            if len(path) == len(nums):
                res.append(path)
                return
            for x in counter:
                if counter[x]:
                    counter[x] -= 1
                    dfs(counter, path+[x])
                    counter[x] += 1
        dfs(Counter(nums), [])
        return res

Zhang6260 · 2021-11-30T15:43:57Z

JAVA版本

使用dfs+剪枝，（今天这题使用hash进行去重居然也能通过。。。）

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);
       }
   }
}

Richard-LYF · 2021-11-30T15:44:08Z

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

yibenxiao · 2021-11-30T15:48:24Z

【Day 82】47 全排列 II

代码

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;
    }
};

复杂度

时间复杂度：O(N*N!)

空间复杂度：O(N)

taojin1992 · 2021-11-30T15:57:28Z

Understand:

nums might contain duplicates
return all possible unique permutations in any order

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

Input: nums = [1,1,2]
Output:
[[1,1,2],
 [1,2,1],
 [2,1,1]]
3!/2!

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
3!

Input: nums = [1,1,2,2]
4!/(2!*2!)=6
[1,1,2,2],[1,2,1,2],[1,2,2,1]
[2,1,1,2],[2,1,2,1],[2,2,1,1]

Input: [1]
[1]

Match & Plan:

use boolean[] visited to record the visited status

How to avoid duplicated permutation? 

first sort the array to group same values together
focus on the case [a1,a2,a3,b1,b2], boolean[] visited

if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]): continue
!visited[i-1] means nums[i-1] is not used

each level of the recursive tree focuses on filling in the cur-level-th index of curList,
[a1,a2,a3,b1,b2]

if a1 is not used, we won't use a2
if a2 is not used, we won't use a3
a1 is always used before a2; a2 is always used before a3

only if a1 is used in the previous level of the tree, then we can use a2. 


visualization link:
https://tinyurl.com/uama777

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).

Code:

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        boolean[] visited = new boolean[nums.length];
        dfs(result, new ArrayList<>(), nums, visited);
        return result;
    }
    
    private void dfs(List<List<Integer>> result, List<Integer> curList, int[] nums, boolean[] visited) {
        if (curList.size() == nums.length) {
            result.add(new ArrayList(curList));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i-1] && !visited[i-1]) {
                continue;
            }
            if (!visited[i]) {
                visited[i] = true;
                curList.add(nums[i]);
                dfs(result, curList, nums, visited);
                visited[i] = false;
                curList.remove(curList.size() - 1);
            }
        }
    }
}

ForLittleBeauty · 2021-11-30T15:58:36Z

思路

We use dictionary to record the frequency of each number. When generating the permutation, we iterate by the key of the dictionary, permutations that have the same prefix have to use different number in the new level. Thus there will be no repeated permutation.

代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        perm = []
        count = {n:0 for n in nums}
        for n in nums:
            count[n]+=1
        
        def dfs():
            if len(perm) == len(nums):
                result.append(perm[:])
            
            for n in count:
                if count[n]>0:
                    perm.append(n)
                    count[n]-=1
                    dfs()
                    count[n]+=1
                    perm.pop()
        dfs()
        return result

时间复杂度: O(N!*op(res))

空间复杂度: O(N*N!)

BpointA · 2021-11-30T16:29:03Z

思路

全排列剪枝

Python代码

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result=[]
        m=len(nums)
        nums.sort()
        def back(depth,visited,path):
            if depth==m:
                result.append(path[:])
                return
            for i in range(m):
                if i>0 and nums[i]==nums[i-1] and visited[i-1]==0:
                    continue
                if visited[i]==0:
                    visited[i]=1
                    path.append(nums[i])
                    back(depth+1,visited,path)
                    visited[i]=0
                    path.pop()
        path=[]
        visited=[0]*m
        back(0,visited,path)
        return result

shixinlovey1314 · 2021-12-01T04:11:09Z

Title:47. Permutations II

Question Reference LeetCode

Solution

Backtracing, but need to make sure not putting duplications.
First sort the list, and skip the duplicated numbers during processing.

Code

class Solution {
public:
    void swap(int& a, int& b) {
        if (a != b) {
            a ^= b;
            b ^= a;
            a ^= b;
        }
    }
    set<vector<int>> result;
    void helper(vector<int>& nums, int index) {
        if (nums.size() == index) {
            result.insert(nums);
            return;
        }
        
        for (int i = index; i < nums.size(); i++) {
            if (i == index || nums[i] != nums[i - 1]) {
                swap(nums[index], nums[i]);
                helper(nums, index + 1);
                swap(nums[index], nums[i]);
            }
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        std::sort(nums.begin(), nums.end());
        helper(nums, 0);
        return vector<vector<int>>(result.begin(), result.end());
    }
};

Complexity

Time Complexity and Explanation

O(n!)

Space Complexity and Explanation

O(n) for the recursion stack

Bingbinxu · 2021-12-04T13:46:01Z

思路
回溯算法dfs+剪枝
代码(C++)

实现语言: C++
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        if (nums.empty()) return {{}};
        if (nums.size() == 1) return {nums};
        vector<vector<int>> result;
        dfs(nums, result, 0);      
        return result;
    }
private:

    void dfs(vector<int> nums, vector<vector<int>>& result, int startPos) {   
        if (startPos == nums.size() - 1) {  
            result.push_back(nums); 
            return;
        }
        unordered_set<int> usedDict;  /* 记录哪些数已经用过 */
        for (int i = startPos; i < nums.size(); ++i) { 
            swap(nums[i], nums[startPos]);  
            if (!usedDict.count(nums[startPos])) {
                usedDict.insert(nums[startPos]);
                dfs(nums, result, startPos + 1);  
            }
            swap(nums[i], nums[startPos]); 
        }
    }
};

复杂度分析
时间复杂度： O(N*N(N-1)...(N-k+1))
空间复杂度： O(N)

azl397985856 added 剪枝回溯 82 labels Nov 29, 2021

【Day 82 】2021-11-30 - 47 全排列 II #101

【Day 82 】2021-11-30 - 47 全排列 II #101

Comments

azl397985856 commented Nov 29, 2021

47 全排列 II

入选理由

题目地址

前置知识

题目描述

yanglr commented Nov 29, 2021

思路:

方法: 回溯

代码:

复杂度分析:

laurallalala commented Nov 29, 2021

代码

revisegoal commented Nov 29, 2021

Note

Code

Complexity

for123s commented Nov 29, 2021

代码

mixtureve commented Nov 29, 2021

biancaone commented Nov 29, 2021

ai2095 commented Nov 29, 2021

47. Permutations II

Topics

思路

代码 Python

复杂度分析

ZacheryCao commented Nov 29, 2021

Idea

Code

Complexity:

CoreJa commented Nov 29, 2021

思路

代码

yingliucreates commented Nov 29, 2021

Laurence-try commented Nov 29, 2021

JiangyanLiNEU commented Nov 29, 2021

skinnyh commented Nov 29, 2021

Note

Solution

pan-qin commented Nov 29, 2021

Idea:

Complexity:

laofuWF commented Nov 29, 2021

Daniel-Zheng commented Nov 29, 2021

思路

代码(C++)

复杂度分析

zhangzz2015 commented Nov 29, 2021 • edited Loading

思路

关键点

代码

kidexp commented Nov 30, 2021

thoughts

code

complexity

shawncvv commented Nov 30, 2021

思路

代码

tongxw commented Nov 30, 2021

思路

代码

chun1hao commented Nov 30, 2021

wenlong201807 commented Nov 30, 2021

代码块

时间复杂度和空间复杂度

yan0327 commented Nov 30, 2021

GZ712D commented Nov 30, 2021

代码

QiZhongdd commented Nov 30, 2021

joeytor commented Nov 30, 2021

思路

复杂度

pophy commented Nov 30, 2021

思路

Java Code

guangsizhongbin commented Nov 30, 2021 • edited Loading

zhangzz2015 commented Nov 29, 2021 •

edited

Loading

guangsizhongbin commented Nov 30, 2021 •

edited

Loading

ysy0707 commented Nov 30, 2021 •

edited

Loading