Backtracking · 041Medium
Permutations
Given an array nums of distinct integers, return all possible permutations in any order.
Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All integers are distinct.
Examples
permute([1, 2, 3]) -> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] permute([1]) -> [[1]] permute([1, 2]) -> [[1,2], [2,1]] // any order permute([0, -1]) -> [[0,-1], [-1,0]] // negatives are fine permute([1, 2, 3, 4]) -> 24 permutations // exactly n! of them
Edge cases
- A single element yields one permutation.
- There are exactly n! results.
Show the target complexity (spoiler)
- Naive
- Generating candidates randomly until all n! are found is unbounded.
- Target
- O(n * n!) time — backtracking with a used-set, or swapping elements in place.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/10-backtracking/041-permutations.js ./practice c 041