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] <= 10nums are unique.Problem Overview: Given an array of distinct integers, return every possible ordering of those numbers. Each ordering is a permutation. The result must include all n! permutations where n is the array length.
Approach 1: Backtracking (O(n! * n) time, O(n) space)
This is the standard solution expected in interviews. Use backtracking to build permutations incrementally. Start with an empty path, iterate through the array, and choose a number that has not been used yet. Add it to the current path, recurse, then remove it during backtracking to explore the next option.
The key insight is treating permutation generation as a decision tree. At each level you pick one unused element. A boolean visited array or swapping technique ensures each element appears only once in a permutation. Because each permutation has length n and there are n! permutations, the total work is O(n! * n). The recursion stack and auxiliary arrays use O(n) space.
This approach works naturally with problems involving arrays and recursive exploration. It is easy to modify for variants such as permutations with duplicates or permutations with constraints.
Approach 2: Iterative Permutation Generation (O(n! * n) time, O(n! * n) space)
Permutations can also be generated iteratively without recursion. Start with a list containing an empty permutation. For each number in the input array, insert it into every possible position of every existing permutation. If the current permutation length is k, inserting the next number creates k + 1 new permutations.
This approach repeatedly expands the permutation list until all elements are used. For example, starting with [ ], inserting 1 produces [1]. Inserting 2 into every position of [1] gives [2,1] and [1,2]. Continue the process for each element until the permutations reach length n.
The time complexity remains O(n! * n) because every permutation must still be constructed and copied. Space complexity grows to O(n! * n) since all permutations are stored during generation. This approach avoids recursion and can feel more intuitive when thinking in terms of incremental construction.
Recommended for interviews: The backtracking solution is what most interviewers expect. It demonstrates control over recursion, state management, and search-space pruning. The iterative insertion approach still works and shows algorithmic creativity, but backtracking is the most common pattern for permutation and combination problems.
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
This solution provides a C implementation using the backtracking approach. The backtrack function swaps elements to fix positions and calls itself recursively to generate permutations. Whenever a complete permutation is reached (start == numsSize), it is added to the result list. Swapping is undone as part of backtracking when going back up the call stack.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
This C implementation illustrates an iterative method for generating permutations using a next permutation generator. Each permutation is based on modifying and reversing array segments to derive the next permutation sequence, iteratively processed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation. |
| Iterative Permutation Generation | Time Complexity: O(n * n!), iterating through permutations. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking with visited array | O(n! * n) | O(n) | Standard interview solution; best for understanding permutation decision trees |
| Iterative insertion method | O(n! * n) | O(n! * n) | When avoiding recursion or demonstrating iterative construction |
Backtracking: Permutations - Leetcode 46 - Python • NeetCode • 390,029 views views
Watch 9 more video solutions →Practice Permutations with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor