Backtrack

result = []
def backtrack(path, choices):
    if satisfies end condition:
        result.add(path)
        return
 
    for choice in choices:
        make the choice
        backtrack(path, choices)
        withdraw the choice

"""
Permutations using backtrack
"""
def permute(nums: list[int]) -> list[list[int]]:
    ans = []
    track = []
    used = [False] * len(nums)
 
    def backtrack(nums, track, used):
        if len(track) == len(nums):
            ans.append(track.copy())
        for i, num in enumerate(nums):
            if used[i]:
                continue
            track.append(num)
            used[i] = True
            backtrack(nums, track, used)
            track.pop()
            used[i] = False
    
    backtrack(nums, track, used)
    return ans

Caution

Since lists are mutable in Python, when we append a track to result list, avoid appending a reference to the same list track by enforcing a deepcopy with track[:] or track.copy(). Otherwise, when track is modified in subsequent iterations, it also changes the list in ans.