Permutations

01 · Question

Given an array nums of distinct integers, return all possible permutations.

02 · Analysis

A level chooses the value at the next output position. Keep used indices and undo both the used flag and path append after recursion. With n distinct values, there are n! answers of length n: O(n*n!) time/output space, plus O(n) auxiliary space. Returning a shared path reference instead of a snapshot corrupts earlier results.

03 · Solution

Reference solution

1def permute(nums: List[int]) -> List[List[int]]:
2    res = []
3    used = [False] * len(nums)
4    cur = []
5
6    def dfs() -> None:
7        if len(cur) == len(nums):
8            res.append(cur[:])
9            return
10        for i in range(len(nums)):
11            if used[i]:
12                continue
13            used[i] = True
14            cur.append(nums[i])
15            dfs()
16            cur.pop()
17            used[i] = False
18
19    dfs()
20    return res

Subsets

Combination Sum