【Day 82 】2024-06-28 - 47 全排列 II

[azl397985856]

47 全排列 II

入选理由

暂无

题目地址

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

前置知识

• 回溯
• 数组
• 剪枝

  题目描述

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

示例:

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

[CathyShang]

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(x):
            if x == len(nums)-1:
                ans.append(list(nums))
                return
            dic = set()
            for i in range(x, len(nums)):
                if nums[i] in dic:
                    continue
                dic.add(nums[i])
                nums[i], nums[x] = nums[x], nums[i]
                dfs(x+1)
                nums[i], nums[x] = nums[x], nums[i]
        dfs(0)
        return ans

[Dtjk]

class Solution { vector vis;

public: void backtrack(vector& nums, vector<vector>& ans, int idx, vector& 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;
}

};

[zhiyuanpeng]

class Solution:
    def __init__(self):
        self.ans = []

    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        self.n = len(nums)
        counter = collections.Counter(nums)
        self.dfs(nums, [], counter)
        return self.ans

    def dfs(self, nums, path, counter):
        if len(path) == self.n:
            self.ans.append(path.copy())
        for k in counter:
            if counter[k] > 0:
                path.append(k)
                counter[k] -= 1
                self.dfs(nums, path, counter)
                path.pop()
                counter[k] += 1