【Day 82 】2023-08-30 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

• 回溯
• 数组
• 剪枝

  题目描述

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

示例:

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

[GuitarYs]

class Permutations:
    def __init__(self):
        self.result = []

    def permuteUnique(self, nums):
        if not nums:
            return []

        used = [False] * len(nums)
        current_permutation = []
        self.backtrack(sorted(nums), used, current_permutation)

        return self.result

    def backtrack(self, nums, used, current_permutation):
        if len(current_permutation) == len(nums):
            self.result.append(list(current_permutation))
            return

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

            used[i] = True
            current_permutation.append(nums[i])
            self.backtrack(nums, used, current_permutation)
            used[i] = False
            current_permutation.pop()

[Diana21170648]

思路

回溯剪枝，去掉重复解看先处理左边，再处理右边

代码

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

复杂度分析

• 时间复杂度：O(N!*op(res))，其中 N 为数组长度。
• 空间复杂度：O(N*N!)

[Alexno1no2]

class Solution:
    def __init__(self):
        self.res = []  # 用于存储结果
        self.track = []  # 用于存储路径
        self.used = []  # 记录元素是否使用过

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 先排序，让相同的元素靠在一起
        nums.sort()
        self.used = [False] * len(nums)
        self.backtrack(nums)
        return self.res

    def backtrack(self, nums):
        if len(self.track) == len(nums):
            self.res.append(self.track.copy())
            return

        for i in range(len(nums)):
            if self.used[i]:
                continue
            # 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
            if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
                continue
            self.track.append(nums[i])
            self.used[i] = True
            self.backtrack(nums)
            self.track.pop()
            self.used[i] = False

[Beanza]

class Solution: def init(self): self.res = [] # 用于存储结果 self.track = [] # 用于存储路径 self.used = [] # 记录元素是否使用过

def permuteUnique(self, nums: List[int]) -> List[List[int]]:
    # 先排序，让相同的元素靠在一起
    nums.sort()
    self.used = [False] * len(nums)
    self.backtrack(nums)
    return self.res

def backtrack(self, nums):
    if len(self.track) == len(nums):
        self.res.append(self.track.copy())
        return

    for i in range(len(nums)):
        if self.used[i]:
            continue
        # 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置
        if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
            continue
        self.track.append(nums[i])
        self.used[i] = True
        self.backtrack(nums)
        self.track.pop()
        self.used[i] = False

[Fuku-L]

代码

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