Permutations
Module 16 · Recursion & Backtracking
Problem
Given an array nums of distinct integers, return all possible
permutations — every ordering of the elements. You may return the answer
in any order.
Examples
Example 1
nums = [1,2,3]Output[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Example 2
nums = [0,1]Output[[0,1],[1,0]]Example 3
nums = [1]Output[[1]]Constraints
1 ≤ n ≤ 6 · all elements distinct · values in ±10. (Even smaller n than Subsets — because n! grows even faster than 2ⁿ.)
Attempt it first
You just wrote Subsets with a start index. Permutations looks similar but
has one decisive difference that breaks the start-index approach entirely.
Before reading on, figure out what it is by asking: in Subsets, does
[1,2] differ from [2,1]? In Permutations, does it? The answer to
that one question determines the entire structure of the solution. Try to
write it, and if you find yourself reaching for a start index, stop and
ask what that index was actually for.