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

Permutations

Return all possible permutations of a distinct integer array.

LeetCode ↗

Approach: DFS (Backtracking)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Return all possible permutations of a distinct integer array.

Constraints

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

Solution — DFS (Backtracking)

O(n!) O(n)

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)