LeetEye LeetEye
Hard Backtracking ~5 min

Permutations

backtracking permutations

Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

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 2
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Key Insight

At each position, choose from remaining unused elements. Track what's been used.

At each position, try all unused elements. Add to result when length = n. Unlike subsets, consider ALL unused elements at each level.

How to Approach This Problem

Pattern Recognition: When you see keywords like permutations backtracking, think Backtracking.

Step-by-Step Reasoning

1 For n distinct elements, total permutations:
Answer: n!
n choices for first, n-1 for second, ... = n!
2 In a permutation, each element:
Answer: Must appear exactly once
Permutation = rearrangement of ALL elements.
3 To ensure each element appears once, we:
Answer: Track used indices/elements
Know what's available vs. already placed.
4 We add current permutation when:
Answer: It has length n
Permutation must include all n elements.
5 At each recursion level, we consider:
Answer: All unused elements
Unlike subsets/combinations, order matters. Any unused element can go in current position.

Solution

def permute(nums: List[int]) -> List[List[int]]:
    result = []
    
    def backtrack(current, used):
        if len(current) == len(nums):
            result.append(current[:])
            return
        
        for i in range(len(nums)):
            if i in used:
                continue
            current.append(nums[i])
            used.add(i)
            backtrack(current, used)
            current.pop()
            used.remove(i)
    
    backtrack([], set())
    return result

Complexity Analysis

Time O(n * n!)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice Backtracking problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye