Permutations

LeetCode 46 · View on LeetCode

Backtracking with a used-set. At each position, try every unused number. When the path length equals the input length, record the permutation.

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    def backtrack(path: list[int], used: set[int]):
        if len(path) == len(nums):
            result.append(path[:])
            return
        for num in nums:
            if num not in used:
                used.add(num)
                path.append(num)
                backtrack(path, used)
                path.pop()
                used.discard(num)
    backtrack([], set())
    return result

if __name__ == '__main__':
    print(permute([1, 2, 3]))
    # [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    print(permute([0, 1]))
    # [[0,1],[1,0]]