Skip to content

Files

Failed to load latest commit information.

Latest commit

 Cannot retrieve latest commit at this time.

History

History

剑指 Offer II 084. 含有重复元素集合的全排列

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 
 
 
comments edit_url
true

题目描述

给定一个可包含重复数字的整数集合 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

 

注意:本题与主站 47 题相同: https://leetcode.cn/problems/permutations-ii/

解法

方法一

Python3

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

        def dfs(u):
            if u == n:
                res.append(path.copy())
                return
            for i in range(n):
                if used[i] or (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]):
                    continue
                path[u] = nums[i]
                used[i] = True
                dfs(u + 1)
                used[i] = False

        dfs(0)
        return res

Java

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

    private void dfs(
        int u, int n, int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> res) {
        if (u == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            dfs(u + 1, n, nums, used, path, res);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

C++

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

    void dfs(int u, int n, vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
        if (u == n) {
            res.emplace_back(path);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            path[u] = nums[i];
            used[i] = true;
            dfs(u + 1, n, nums, used, path, res);
            used[i] = false;
        }
    }
};

Go

func permuteUnique(nums []int) [][]int {
	n := len(nums)
	res := make([][]int, 0)
	path := make([]int, n)
	used := make([]bool, n)
	sort.Ints(nums)
	dfs(0, n, nums, used, path, &res)
	return res
}

func dfs(u, n int, nums []int, used []bool, path []int, res *[][]int) {
	if u == n {
		t := make([]int, n)
		copy(t, path)
		*res = append(*res, t)
		return
	}
	for i := 0; i < n; i++ {
		if used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
			continue
		}
		path[u] = nums[i]
		used[i] = true
		dfs(u+1, n, nums, used, path, res)
		used[i] = false
	}
}

C#

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        var results = new List<IList<int>>();
        var temp = new List<int>();
        var count = nums.GroupBy(n => n).ToDictionary(g => g.Key, g => g.Count());
        Search(count, temp, results);
        return results;
    }

    private void Search(Dictionary<int, int> count, IList<int> temp, IList<IList<int>> results)
    {
        if (!count.Any() && temp.Any())
        {
            results.Add(new List<int>(temp));
            return;
        }
        var keys = count.Keys.ToList();
        foreach (var key in keys)
        {
            temp.Add(key);
            --count[key];
            if (count[key] == 0) count.Remove(key);
            Search(count, temp, results);
            temp.RemoveAt(temp.Count - 1);
            if (count.ContainsKey(key))
            {
                ++count[key];
            }
            else
            {
                count[key] = 1;
            }
        }
    }
}

Swift

class Solution {
    func permuteUnique(_ nums: [Int]) -> [[Int]] {
        var res = [[Int]]()
        var path = [Int]()
        var used = [Bool](repeating: false, count: nums.count)
        let sortedNums = nums.sorted()
        dfs(0, sortedNums.count, sortedNums, &used, &path, &res)
        return res
    }

    private func dfs(
        _ u: Int, _ n: Int, _ nums: [Int], _ used: inout [Bool], _ path: inout [Int], _ res: inout [[Int]]
    ) {
        if u == n {
            res.append(path)
            return
        }
        for i in 0..<n {
            if used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue
            }
            path.append(nums[i])
            used[i] = true
            dfs(u + 1, n, nums, &used, &path, &res)
            used[i] = false
            path.removeLast()
        }
    }
}