0046-permutations¶
Try it on leetcode
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]]
Constraints:
1 <= nums.length <= 6-10 <= nums[i] <= 10- All the integers of
numsare unique.
Solution(Python)¶
class Solution:
def permute(self, nums: list[int]) -> list[list[int]]:
# [1,2,3]
# i = 0
# swap 1 2
# swap 1 3
# i= 1
# 2 1
# 2 3
res = []
n = len(nums)
def backtrack(i, candidate): # 0, [1,2,3]
if i == n:
res.append(candidate.copy()) # [1,2,3]
for j in range(i , n):# 1 -> 2
candidate[i], candidate[j] = candidate[j], candidate[i] # [2,1,3]
backtrack(i+1, candidate)
candidate[i], candidate[j] = candidate[j], candidate[i]
backtrack(0, nums.copy())
return res
# # 0 1
# []
# 0 1
#