Is Permutations II easy or hard?

Permutations II is generally classified as a medium difficulty problem. Basic permutation generation is straightforward, but handling duplicates correctly requires careful pruning logic during backtracking. Many candidates struggle with the duplicate-skipping condition.

Permutations II Python/Java solution

Python and Java implementations usually follow the same pattern: sort the input array, track visited indices with a boolean array, and build permutations recursively. During iteration, skip numbers that are the same as the previous element if the previous element was not used in the current recursion path.

How to solve Permutations II in O(n)?

Permutations II cannot be solved in O(n) time because generating permutations inherently requires factorial work. Any correct algorithm must output every valid permutation, which is up to n! results. Efficient solutions focus on pruning duplicates using sorting or hash sets during backtracking.

What is the best approach for Permutations II?

Backtracking with a sorted array and a used[] tracking array is the most widely used solution. Sorting groups duplicates together, and the algorithm skips a number if it matches the previous number that was not used in the current recursion branch. This prevents duplicate permutations while still exploring all valid arrangements. Time complexity is O(n! * n).

Is Permutations II asked at Google/Amazon/Meta?

Permutation generation and duplicate-handling backtracking problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include generating combinations, subsets with duplicates, and permutation generation with constraints. Interviewers use these problems to evaluate recursion and pruning strategies.

What data structure is used in Permutations II?

The solution primarily uses arrays and recursion. A boolean used[] array or a HashSet is typically added to control duplicates during backtracking. Sorting the array beforehand is also a key step because it allows simple duplicate checks during iteration.

What is the time complexity of Permutations II?

The time complexity is O(n! * n). There can be up to n! permutations in the worst case when all numbers are distinct, and building each permutation requires O(n) work. Duplicate values reduce the actual number of permutations but the upper bound remains factorial.

Description Solution Video 11:47

47. Permutations II

Medium64.3% acceptance9 companies

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

Asked at 9 companies

Tiktok LinkedIn Amazon Microsoft Bloomberg Apple

Google Goldman Sachs Meta

Topics

Array Backtracking

11:47

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

47. Permutations II

Asked at 9 companies

Topics

Similar problems