46. Permutations
Description
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
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]] Example 3:
Input: nums = [1] Output: [[1]]
Thinking
This question is more like a tree problem. like the tree below:
dfs(0): nums = [1,2,3]
|
|-- i=0: swap(0,0) -> [1,2,3]
| |
| |-- dfs(1)
| |-- i=1: swap(1,1) -> [1,2,3]
| | |-- dfs(2): append [1,2,3]
| |-- i=2: swap(1,2) -> [1,3,2]
| |-- dfs(2): append [1,3,2]
|
|-- i=1: swap(0,1) -> [2,1,3]
| |
| |-- dfs(1)
| |-- i=1: swap(1,1) -> [2,1,3]
| | |-- dfs(2): append [2,1,3]
| |-- i=2: swap(1,2) -> [2,3,1]
| |-- dfs(2): append [2,3,1]
|
|-- i=2: swap(0,2) -> [3,2,1]
|
|-- dfs(1)
|-- i=1: swap(1,1) -> [3,2,1]
| |-- dfs(2): append [3,2,1]
|-- i=2: swap(1,2) -> [3,1,2]
|-- dfs(2): append [3,1,2]We swap the current position index with each possible candidate i from index to the end. They can be seen as left and right pointers: index determines which position we're filling, and i tries different numbers to place there.
Before the recursive call, we swap nums[i] and nums[index] to try placing a new number at position index. If we reach the last position (index == len(nums) - 1), we add the current permutation to the answer list.
After recursion, we swap back to restore the original state (backtracking).
Code
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
# index
def dfs(index):
# Reach the last element
if index == len(nums) - 1:
res.append(list(nums))
return
for i in range(index, len(nums)):
nums[i], nums[index] = nums[index], nums[i]
dfs(index + 1)
nums[i], nums[index] = nums[index], nums[i]
res = []
dfs(0)
return res贡献者
最近更新
Involution Hell© 2026 byCommunityunderCC BY-NC-SA 4.0
46. Permutations
LeetCode 46. Permutations — solution using backtracking with element swapping to generate all permutations via recursion and state restoration (backtracking), enabling full permutation output for arrays without duplicate numbers. Suitable for algorithm learners and job seekers preparing for interviews who want to reinforce backtracking and DFS skills.
538. Convert BST to Greater Sum Tree
LeetCode 538. Convert BST to Greater Sum Tree — reverse in-order traversal with cumulative sum, updating each node to the sum of all greater values; for developers preparing for tree manipulation and BST problems.