Permutations — DSA-30

Permutations medium

Description

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Examples

> Case 1:
    nums = [1, 2, 3]
    Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
 
> Case 2:
    nums = [0, 1]
    Output: [[0,1], [1,0]]
 
> Case 3:
    nums = [1]
    Output: [[1]]

Constraints

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All integers are unique.

State design

Partial solution? path — the chosen prefix so far. Plus a used[] boolean array.
Complete? When len(path) == n.
Choices? Every unused index.
Legality? used[i] must be false.
Undo? Pop the element from path AND mark used[i] = false.

Code — `used[]` array variant

In-place swap variant (no `used[]`)

Treat nums[0..start) as the fixed prefix and nums[start..n) as the pool. Swap each pool element into position start, recurse, swap back.

O(1) auxiliary space (besides the output). Trade-off: handling duplicates needs an explicit per-call seen-set.

Handling duplicates (Permutations II preview)

If the input has repeats — nums = [1, 1, 2] — the bare template generates the same permutation multiple times. The fix:

Sort the input.
In the for-loop, skip i if nums[i] == nums[i - 1] AND !used[i - 1] — meaning “the previous identical value isn’t currently picked in this branch.”

nums.sort()
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
    ...

This enforces a canonical “always pick identical values left-to-right” rule that kills all duplicates without ever generating them.

Analysis

Time: O(n! × n) — n! permutations, O(n) to copy each.
Space: O(n) recursion + used[].

Same skin

Permutations II — duplicates in input; see fix above.
Next Permutation — find the lexicographically next permutation in-place (O(n) two-pointer trick, not backtracking).
Beautiful Arrangement — permutation with a divisibility constraint on each position.

Subsets Combination Sum