46. Permutations

Problem¶

Return every ordering of a list of distinct integers.

Example:

in:  nums = [1, 2, 3]
out: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
note: same values, different orders; any output order is valid

Key trick¶

Use backtracking:

• Choose one unused number.
• Add it to the current permutation.
• Recurse.
• Undo the choice.

A clean interview version swaps in-place so you avoid extra sets and repeated differences.

Trap¶

Common mistakes:

• Appending path directly instead of a copy, which makes all answers mutate together.
• Forgetting to undo the choice after recursion.
• Recomputing unused elements with set difference on every call, adding unnecessary overhead.
• Assuming output order matters.

Why is it interesting?¶

It is the classic backtracking template:

• build partial answer
• recurse
• undo

It also tests whether you can reason about generating all \(n!\) results, so exponential output is expected.

Python solution¶

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        res = []

        def backtrack(i):
            # If we fixed every position, we built one full permutation.
            if i == n:
                res.append(nums[:])  # copy current arrangement
                return

            # Put each remaining number into position `i`.
            for j in range(i, n):
                nums[i], nums[j] = nums[j], nums[i]
                backtrack(i + 1)
                nums[i], nums[j] = nums[j], nums[i]  # undo

        backtrack(0)
        return res

    def permute_2(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in itertools.permutations(nums)]

Complexity:

• Time: \(O(n \cdot n!)\)
• Space: \(O(n)\) auxiliary, excluding output

Library alternative:

from itertools import permutations


class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        return [list(p) for p in permutations(nums)]

Comment on my solution¶

Your solution is close and the backtracking idea is correct.

Issues:

• result.append(path) is a bug.
  • You must append a copy:

result.append(path[:])

• nums_set.difference(used) on every recursion is unnecessary extra work.
• Tracking used as values works here only because values are distinct.
• In-place swapping is simpler and more standard for this question.

## Solution
# WRONG
# I should use path.copy() when appending to result
class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        nums_set = set(nums)
        result = []
        path = []

        def dfs(used):
            if len(used) == len(nums):
                result.append(path)
                return
            complement = nums_set.difference(used)
            for x in complement:
                path.append(x)
                used.add(x)
                dfs(used)
                used.remove(x)
                path.pop()

        dfs(set())
        return result


Solution().permute([1,2])

Your fixed version would be:

class Solution:
    def permute(self, nums: list[int]) -> list[list[int]]:
        nums_set = set(nums)
        result = []
        path = []

        def dfs(used):
            if len(used) == len(nums):
                result.append(path[:])
                return

            for x in nums_set.difference(used):
                path.append(x)
                used.add(x)
                dfs(used)
                used.remove(x)
                path.pop()

        dfs(set())
        return result

Extra¶

About naming intermediary functions in dfs/backtracking leetcode problems¶

In leetcode dfs/backtracking problems, solutions often use intermediary functions to do the dfs/backtracking steps: they are called dfs or backtracking. Here's an example:

class Solution: def permute(self, nums: list[int]) -> list[list[int]]: result = [] def backtrack(i): if i == len(nums): result.append(nums[:]) # copy current arrangement return for j in range(i, len(nums)): nums[i], nums[j] = nums[j], nums[i] backtrack(i + 1) nums[i], nums[j] = nums[j], nums[i] # undo backtrack(0) return result

When to use dfs vs. backtrack as name for that intermediary function? Is there some rational for it? What the most idiomatic and straightforward to underdand?

• Use dfs when emphasizing graph or tree traversal: visit a node, then recursively visit its children or neighbors.
• Use backtrack when emphasizing search over choices: make a choice, recurse, then undo that choice to try another.
• Backtracking is typically DFS over a decision tree, so both names may be technically correct. Choose the name that expresses the algorithm’s intent.

For your permutation example, backtrack is more idiomatic because it explicitly performs choose-recurse-undo:

nums[i], nums[j] = nums[j], nums[i]  # choose
backtrack(i + 1)                     # recurse
nums[i], nums[j] = nums[j], nums[i]  # undo

Rule of thumb:

• Traversing existing nodes or cells: dfs
• Constructing candidates through choices and undoing state: backtrack
• If a more specific name is clear, prefer it, such as generate, search, or visit