Permutations

The problem description can be found in LeetCode.

Approach

This is a classic Backtracking problem.

We can again build our space tree and simply avoid to visit the same number twice.

Solution

from typing import List, Set


class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(seen: Set[int], curr: List[int], perms: List[List[int]]) -> None:
            if len(curr) == len(nums):
                perms.append(curr.copy())
                return

            for num in nums:
                if num in seen:
                    continue

                seen.add(num)
                curr.append(num)
                dfs(seen, curr, perms)
                seen.remove(num)
                curr.pop()

        ans: List[List[int]] = []
        dfs(set(), [], ans)

        return ans

Complexity

• Time: $O(nn!)$
• Space: $O(n)$

Where $n$ is the size of the nums list.