LeetCode

Appearance

47. Permutations II ​

题目 ​

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

 

Example 1:

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

Example 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]]

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
Related Topics
  • 数组
  • 回溯
  • 排序

  • 👍 1721
  • 👎 0

    • 思路 ​

    本题和 46 题的升级题，多了重复的元素的处理

    数组中存在重复元素可以进行排序操作，用于后续跳过这个重复操作

    注意跳过重复的元素时

    • 条件判断，和上一个元素进行比较
    • 命中操作，只需跳过该元素，不用标记 used

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        def backtrack(path, used):
            if len(path) == len(nums):
                res.append(path[:])
                return

            for i, num in enumerate(nums):
                if i > 0 and nums[i] == nums[i - 1] and used[i - 1]:
                    continue

                if not used[i]:
                    used[i] = True
                    path.append(num)
                    backtrack(path, used)
                    path.pop()
                    used[i] = False



        backtrack([], [False] * len(nums))
        return res


# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

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