Permutations

A permutation is an arrangement of elements where order matters: [1, 2, 3] and [3, 2, 1] are different. With n distinct elements there are n! permutations, because there are n choices for the first position, n - 1 for the second, and so on.

Unlike subsets, every position may take any element that has not been used yet, not just elements to the right. So the template loops over all indices and keeps a used array (or set) to know which elements are already in the path.

If the input has duplicates, like [1, 1, 2], swapping the two 1s gives the same permutation. Sorting and a careful skip rule produce each distinct permutation once: 3! / 2! = 3 of them here.

1. 1State: path (the arrangement so far) and used[i] (is nums[i] already placed).
2. 2Goal: when len(path) == n, record a copy.
3. 3Choices: every index i with used[i] False. Mark it used, append nums[i], recurse, then pop and unmark.
4. 4Each level fills one position, so the tree has depth n and n * (n - 1) * ... * 1 = n! leaves.
5. 5For duplicates: sort, and skip nums[i] if it equals nums[i - 1] and nums[i - 1] is not currently used. This forces equal values to be placed in their original order, so each distinct arrangement appears once.
6. 6Alternative: swap-based permutation, which swaps nums[start] with each nums[i] for i >= start, recurses on start + 1, and swaps back; it uses no extra used array.

def permutations(nums):
    nums = sorted(nums)                 # sorting groups equal values
    result, path = [], []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):
            result.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue                # duplicate copy used out of order
            used[i] = True
            path.append(nums[i])
            backtrack()
            path.pop()
            used[i] = False

    backtrack()
    return result

print(permutations([1, 2, 3]))  # 6 orderings
print(permutations([1, 1, 2]))  # [[1, 1, 2], [1, 2, 1], [2, 1, 1]]

This is the standard used-array template plus one extra check for duplicates. With distinct input the duplicate check never fires. With repeated values it sorts, then refuses to place a duplicate value while its identical left neighbour is still unused, so the copies of a value are always placed left to right and each distinct ordering appears once. For [1, 1, 2] it returns [1, 1, 2], [1, 2, 1], [2, 1, 1].

Cost: n! permutations, each copied in O(n), so O(n * n!) time. Extra space O(n) for the path, used array and recursion depth.