Permutations

Return all orderings (permutations) of the given distinct integers. At each position, choose the next unused element in index order, which produces the order shown below.

permutations(nums)

Input format: space-separated integers. Output: each permutation's values joined by spaces, permutations separated by ;.

Examples

[1, 2]      // → "1 2;2 1"
[1, 2, 3]   // → "1 2 3;1 3 2;2 1 3;2 3 1;3 1 2;3 2 1"
[]          // → ""   (one empty permutation)

Walkthrough

Thinking it through

A permutation is a complete arrangement of all n elements. There are n! of them: n choices for the first slot, n-1 for the second, down to 1 for the last. Build one arrangement at a time, slot by slot, trying every not-yet-placed element at each slot.

The decision tree

The root is an empty arrangement. Each node has one child per unused element on the path from root to that node — choosing a child places that element in the next slot. A leaf is reached once every element is placed, corresponding to one complete permutation. Every root-to-leaf path is a distinct choice sequence, and every ordering corresponds to exactly one such path — walking the whole tree produces every permutation exactly once.

Why backtracking is the right tool

Maintain a current partial arrangement and which elements are used:

If the arrangement is full, you've reached a leaf — save a copy.
Otherwise try each element in turn, skipping used ones. For a free one, mark it used, append it, recurse.
After the recursive call returns, undo: remove the element, mark it unused, so the loop can try a different element in that slot.

That undo step is what makes it backtracking rather than one-shot recursion — the same slot gets tried with every candidate, reusing one array and one used-list instead of allocating fresh state per branch.

Why this covers everything, without duplicates

Each slot's loop considers every unused element exactly once — nothing skipped. Undoing the used-flag after each branch makes rejected elements available again for other branches, essential since different permutations reuse elements in different slots. Every arrangement corresponds to a unique "pick the next unused element" sequence, and the recursion tries every one — exactly n! permutations, each produced once.

Why not simpler alternatives

You could remove one element from a pool and prepend it to permutations of the rest — equally valid, but it copies/removes from arrays at every level. The used-array approach just flips boolean flags, making each branch cheap to enter and leave.

main.py

Auto-saved

Console

Press Run to execute your code, or Submit to test and complete this problem.