How does sorting assist with generating unique permutations in Permutations II?

Sorting ensures duplicate numbers are adjacent, which allows the backtracking algorithm to skip repeated elements efficiently, preventing duplicate permutations from being generated.

What is the role of the used-element tracking array in this problem?

The boolean array tracks which elements are included in the current permutation path. Skipping elements that are already used in the current branch avoids repeating numbers and maintains correct sequences.

How does pruning prevent redundant recursive calls in backtracking?

Pruning skips elements that are identical to the previous unused element, reducing the number of unnecessary recursive calls and ensuring each branch explores a unique permutation path.

Can Permutations II handle negative numbers and zeros?

Yes, the algorithm correctly handles negative numbers, zeros, and duplicates as long as the array is sorted first and backtracking with pruning is applied to skip duplicates.

Why is backtracking with pruning the preferred pattern for this problem?

Backtracking systematically explores all possible sequences, and pruning duplicates prevents repeated permutations, making it both correct and efficient for arrays with repeated numbers.

#47

Medium

auto_awesome回溯·pruning

LeetCode 题解工作台

全排列 II

给定一个可包含重复数字的序列 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…

数组回溯排序

题目描述

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

lightbulb

解题思路

方法一：排序 + 回溯

我们可以先对数组进行排序，这样就可以将重复的数字放在一起，方便我们进行去重。

然后，我们设计一个函数 $\textit{dfs}(i)$ ，表示当前需要填写第 $i$ 个位置的数。函数的具体实现如下：

如果 $i = n$ ，说明我们已经填写完毕，将当前排列加入答案数组中，然后返回。
否则，我们枚举第 $i$ 个位置的数 $nums[j]$ ，其中 $j$ 的范围是 $[0, n - 1]$ 。我们需要保证 $nums[j]$ 没有被使用过，并且与前面枚举的数不同，这样才能保证当前排列不重复。如果满足条件，我们就可以填写 $nums[j]$ ，并继续递归地填写下一个位置，即调用 $\textit{dfs}(i + 1)$ 。在递归调用结束后，我们需要将 $nums[j]$ 标记为未使用，以便于进行后面的枚举。

在主函数中，我们首先对数组进行排序，然后调用 $\textit{dfs}(0)$ ，即从第 0 个位置开始填写，最终返回答案数组即可。

时间复杂度 $O(n \times n!)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组的长度。需要进行 $n!$ 次枚举，每次枚举需要 $O(n)$ 的时间来判断是否重复。另外，我们需要一个标记数组来标记每个位置是否被使用过，因此空间复杂度为 $O(n)$ 。

相似题目：

46. 全排列

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        def dfs(i: int):
            if i == n:
                ans.append(t[:])
                return
            for j in range(n):
                if vis[j] or (j and nums[j] == nums[j - 1] and not vis[j - 1]):
                    continue
                t[i] = nums[j]
                vis[j] = True
                dfs(i + 1)
                vis[j] = False

        n = len(nums)
        nums.sort()
        ans = []
        t = [0] * n
        vis = [False] * n
        dfs(0)
        return ans

speed

复杂度分析

指标	值
时间	\mathcal{O}\big(\sum_{k = 1}^{N}{P(N, k)}\big)
空间	\mathcal{O}(N)

psychology

面试官常问的追问

外企场景

question_mark
Do you understand how sorting helps prune duplicate paths in backtracking for this problem?
question_mark
Can you implement the used-element tracking to avoid repeated sequences efficiently?
question_mark
Will you explain how skipping a duplicate number affects the recursion tree and total permutations?

warning

常见陷阱

外企场景

error
Failing to sort the input array before backtracking, causing duplicate permutations to appear in the output.
error
Not properly skipping a duplicate element when the previous identical element hasn't been used, leading to repeated sequences.
error
Modifying the current path without restoring state after recursion, resulting in incorrect permutations being carried forward.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Generate all unique subsets of an array with possible duplicates, requiring backtracking with pruning similar to this problem.
arrow_right_alt
Permutations without duplicates: Given an array with distinct numbers, generate all permutations, a simpler variant without duplicate checks.
arrow_right_alt
Count the number of unique permutations for large N with duplicates, focusing on combinatorial calculation rather than explicit generation.

help

常见问题

外企场景

继续练习

#49 字母异位词分组 #37 解数独 #75 颜色分类