Permutations

Problem

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

Examples

The brute-force approach

For n elements, generate every sequence of indices from 0 to n-1. Keep only the sequences that use each index exactly once (i.e., they are valid permutations of the index array). Build the corresponding element array for each valid sequence.

result = []

for each sequence of length n from {0..n-1}:
    if sequence has no repeated indexes:
        result.append([nums[i] for i in sequence])

return result

You'd be generating n^n sequences to find n! valid ones. For n=6 that's 46,656 candidates to yield 720 permutations. The ratio gets worse as n grows. There is no pruning, you generate the full sequence and check validity at the end.

Spotting the pattern

This is a Backtracking problem. The key question to ask yourself:

Subsets records a snapshot at every call. Permutations records only at the leaves. What condition marks a 'leaf' in the permutation decision tree?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.