Permutations
Last Updated: November 14, 2025
Problem Description
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
numsare unique.
Solve it on LeetCode
Approaches
1. Recursive Backtracking
The basic idea for generating all permutations of an array is to swap each element with every other element and then recursively call the function for the next depth. The permutations are generated by exploring the problem's decision tree depth-first. In each recursive call, we will swap elements and call the function for the next element. Once all elements are considered, we add the current permutation into our result list.
Intuition:
- Start with the first element and generate permutations with all other elements.
- Use a recursive function to explore all permutations.
- Swap elements at each recursive level to fix one and permute the rest.
- Keep track of current permutation and used elements.
- Backtrack and undo the swap to explore different permutations.
Code:
- Time Complexity: O(n * n!), where n is the length of
nums. We have n! permutations and for each permutation, we copy the permutation list to results. - Space Complexity: O(n) due to the recursion stack and storage for the permutations being created.
2. Iterative using Insertion
This approach builds permutations iteratively by repeatedly inserting a new element into existing permutations generated so far. It makes use of lists and creates new permutations by inserting the current element in every possible position within each existing permutation.
Intuition:
- Start with an empty permutation list.
- Gradually build it by inserting each new element into all possible positions of existing permutations.
- This process builds all permutations without recursion.
Code:
- Time Complexity: O(n * n!), where n is the length of
nums. This is because for each new number, all previous permutations are expanded. - Space Complexity: O(n * n!), as we store all permutations explicitly.