permutations.py

from typing import List


class Solution:
    """LeetCode #46 - Permutations (Medium)
    https://leetcode.com/problems/permutations/

    Return every ordering of `nums` (all values distinct). There are n! of them.
    """

    def permute(self, nums: List[int]) -> List[List[int]]:
        """Backtracking over positions, with a `used` flag per element.

        Key insight and the contrast worth understanding: in Subsets and
        Combination Sum we passed a `start` index to *forbid* looking backwards,
        because order did not matter there. Here order is the entire point, so
        every branch must consider **all** elements - and the only thing to
        exclude is an element already placed in the current permutation. That is
        what `used` tracks.

        A permutation is complete when its length reaches n; at that moment
        every element has been used exactly once.

        Same choose / explore / undo rhythm, except now two pieces of state get
        restored on the way out - the list and the flag. Forgetting
        `used[i] = False` is the classic bug: it silently produces only one
        permutation.

        Time:  O(n * n!) - n! permutations, each copied in O(n).
        Space: O(n)      - recursion depth, the flags and the working list.
        """
        result = []
        current = []
        used = [False] * len(nums)

        def backtrack() -> None:
            if len(current) == len(nums):
                result.append(current[:])     # snapshot, not a reference
                return

            for i in range(len(nums)):
                if used[i]:
                    continue                  # already placed in this permutation

                used[i] = True                # choose
                current.append(nums[i])

                backtrack()                   # explore

                current.pop()                 # undo - both pieces of state
                used[i] = False

        backtrack()
        return result