#73 Medium Time O(n!) Space O(n) Animated

Permutations

Return all possible permutations of a distinct integer array.

LeetCode ↗

Tutor Mode Build the mental model before you memorize the code.

1 Predict
2 Trace
3 Explain
4 Implement

Pattern Backtracking: choose, explore, unchoose

Build one partial answer at a time and undo each choice so sibling branches start clean.

Approach: DFS (Backtracking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Core Insight

Build one partial answer at a time and undo each choice so sibling branches start clean.

Common Pitfall

Copy a completed path before appending it to results; later mutations must not alter it.

Description

Return all possible permutations of a distinct integer array.

Constraints

Time Complexity: O(n!)
Space Complexity: O(n)

Solution — DFS (Backtracking)

TimeO(n!) SpaceO(n)

Implementation Plan

Translate the invariant into these small, testable moves.

Choose a candidate.
Record the choice.
Explore the next decision.
Undo the choice before trying the next candidate.

def permute(nums):
    res = []
    
    if len(nums) == 1:
        return [nums.copy()]
        
    for i in range(len(nums)):
        n = nums.pop(0)
        perms = permute(nums)
        
        for perm in perms:
            perm.append(n)
        res.extend(perms)
        nums.append(n)
        
    return res

Combination Sum

Subsets II

Permutations

Steps

Description

Constraints

Tags

Solution — DFS (Backtracking)