Start by choosing each number as the first element and recursively backtrack to build full permutations. Track used elements to avoid revisiting and prune paths that cannot yield new permutations. This method ensures all valid orderings are generated efficiently while minimizing redundant recursion.
Problem Statement
Given an array of distinct integers nums, generate every possible permutation and return them in any order. Each permutation should contain all elements of nums exactly once.
For example, with nums = [1,2,3], valid outputs include [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. Constraints ensure 1 <= nums.length <= 6, -10 <= nums[i] <= 10, and all elements are unique.
Examples
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 details omitted.
Example 2
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example details omitted.
Example 3
Input: nums = [1]
Output: [[1]]
Example details omitted.
Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
Solution Approach
Backtracking with a 'used' marker array
Track which elements are already included in the current permutation using a boolean array. At each step, iterate through nums and skip elements marked as used. Recursively add unused elements and backtrack by unmarking them once the recursion unwinds.
Recursive swap method
Swap each element with the current position index to generate permutations in-place. After recursive calls, swap back to restore the array state. This avoids extra space for a 'used' array and allows permutations to be built directly within nums.
Pruning to prevent redundant paths
Even with distinct elements, pruning can stop recursion early if certain paths cannot lead to new permutations. For larger inputs or extensions with duplicate elements, pruning prevents revisiting combinations that are already included in the result list.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n! * n) due to generating n! permutations and copying them into the result. Space complexity is O(n) for recursion depth and O(n) for used markers or swaps.
What Interviewers Usually Probe
- Candidate immediately considers backtracking and marks elements used for recursion.
- Candidate identifies recursion depth and correctly restores state during backtracking.
- Candidate demonstrates understanding of how to prune or skip redundant recursion paths.
Common Pitfalls or Variants
Common pitfalls
- Failing to restore element state after recursive calls leads to incorrect permutations.
- Ignoring the need for a 'used' marker or proper swap tracking can cause duplicates or missing permutations.
- Not handling recursion base cases correctly, especially when building the final permutation list.
Follow-up variants
- Generate permutations of a string of distinct characters instead of integers.
- Generate k-length permutations from n elements instead of full-length permutations.
- Generate permutations allowing duplicate elements and remove duplicates from the result list.
How GhostInterview Helps
- Highlights the correct backtracking recursion flow and tracks used elements automatically.
- Identifies where pruning can improve efficiency and prevents exploring invalid paths.
- Provides step-by-step construction of all permutations with debugging insights for recursion mistakes.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main strategy to solve the Permutations problem?
Use backtracking search with a 'used' marker or in-place swaps, recursively building permutations and pruning invalid paths.
Can I generate permutations without extra space?
Yes, the recursive swap method allows in-place generation of permutations, reducing space usage compared to a separate 'used' array.
How does pruning work in this context?
Pruning skips recursive paths that cannot produce new unique permutations, ensuring the algorithm doesn't redo work unnecessarily.
What are common mistakes in coding this problem?
Not restoring array state after recursion, failing to mark elements as used, and mishandling base cases can cause errors.
How does the backtracking pattern help with permutations?
Backtracking systematically explores all ordering options, building partial solutions while removing invalid choices through pruning and used tracking.
Need direct help with Permutations instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Permutations from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Generate all unique permutations of an array containing duplicates using backtracking and pruning to avoid repeated sequences efficiently.
Open problem page#51 N-QueensSolve the N-Queens problem using backtracking with pruning, exploring all valid board placements while avoiding conflicts efficiently.
Open problem page#40 Combination Sum IIFind all unique combinations of numbers that sum to a target using backtracking with careful pruning to avoid duplicates.
Open problem page