46. Permutations
Permutations (LeetCode 46) 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.
How to solve Permutations
Permutations is a Generate Permutations problem, part of Backtracking Patterns. Generate all permutations using backtracking. Handle duplicates and next permutation.
Work towards the solution in these steps:
- Consider using backtracking as a method to explore all possible arrangements systematically.
- Think about how you can represent the current state of your permutation and which elements are still available to use.
- At each step, try adding an unused element to your current permutation and recurse to build further.
The reference solution runs in O(n * n!) time and O(n * n!) space.
The Permutations solution and editorial walks through the full approach with reference code.
Problem statement
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Example 1:
Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]
Example 3:
Input: nums = [1] Output: [[1]]
Constraints:
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
Topics and companies
Topics: Array, Backtracking.
Reported in interviews at Amazon, Apple, Bloomberg, ByteDance, eBay, Facebook, Google, LinkedIn, Microsoft, Oracle, Paypal, Uber.
How to practise Permutations on Thita.ai
Starter code is provided in C, 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 * n!) time and O(n * n!) space.
Open Permutations in the code editor, or read the Permutations editorial for a worked solution with its approach and complexity analysis.
Where Permutations sits in the DSA pattern sheet
Problems related to Permutations
Other problems that use the same Permutations and Backtracking Patterns techniques:
- Next Permutation — Medium, same subpattern
- Permutation Sequence — Hard, same subpattern
- Permutations II — Medium, same subpattern
- Check if Word Can Be Placed In Crossword — Medium, same pattern
- Combinations — Medium, same pattern
- Combination Sum — Medium, same pattern
Permutations FAQ
What is the LeetCode number of Permutations?
Permutations is LeetCode problem 46, rated Medium.
What pattern is used to solve Permutations?
Permutations is a Generate Permutations problem. It belongs to the Backtracking Patterns pattern, in the Permutations subpattern.
What is the time complexity of Permutations?
The reference solution runs in O(n * n!) time and O(n * n!) space.
Which companies ask Permutations?
Permutations has been reported in interviews at Amazon, Apple, Bloomberg, ByteDance, eBay, Facebook, Google, LinkedIn, Microsoft, Oracle, Paypal, Uber.