Permutations II
Permutations II is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
Problem statement
Implement permuteUnique in the Solution class. The parameter nums contains integers, and a permutation is an arrangement that uses every element of nums exactly once.
Return a JSON-compatible list containing every distinct permutation of nums. If equal integer values occur multiple times, swapping those equal values does not create a new permutation, so duplicate arrangements must appear only once.
The returned permutations may be in any order. Each inner list must have the same length as nums and contain exactly the same values with the same multiplicities.
Example 1:
Input: nums = [2,2,5] Output: [[2,2,5],[2,5,2],[5,2,2]] Explanation: There are three arrangements because the two copies of 2 are indistinguishable.
Example 2:
Input: nums = [-1,3,0] Output: [[-1,0,3],[-1,3,0],[0,-1,3],[0,3,-1],[3,-1,0],[3,0,-1]] Explanation: All three values differ, so every ordering is distinct.
Example 3:
Input: nums = [4,4,4,1] Output: [[1,4,4,4],[4,1,4,4],[4,4,1,4],[4,4,4,1]] Explanation: The repeated 4 values produce only four distinct positions for the single 1.
Constraints:
- 1 <= nums.length <= 8 - -10 <= nums[i] <= 10 - nums may contain repeated integer values - Every returned permutation uses all elements of nums exactly once
Topics and companies
Topics: Array, Backtracking, Recursion, Sorting.
How to practise Permutations II on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n + n · P), where n is nums.size() and P is the number of distinct permutations. time and O(n) auxiliary space excluding the returned result, which itself requires O(n · P) space. space.
Open Permutations II in the code editor, or read the Permutations II editorial for a worked solution with its approach and complexity analysis.
Where Permutations II sits in the DSA pattern sheet
- Backtracking Patterns pattern guide
- Permutations subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Permutations II
Other problems that use the same Permutations and Backtracking Patterns techniques:
- Next Permutation — Medium, same subpattern
- Permutations — Medium, same subpattern
- Permutation Sequence — Hard, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern