Permutations

Permutations 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

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!), where n is the length of nums. There are n! permutations, and each permutation is copied (O(n)) into the results vector. time and O(n * n!), for storing all n! permutations of length n. The recursion stack uses O(n) space. 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

• Backtracking Patterns pattern guide
• Permutations subpattern
• The full DSA patterns sheet
• All coding practice problems

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
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern
• Combination Sum II — Medium, same pattern