You are given nums, a list of distinct integers. Return every permutation of it: every list that
holds each number of nums exactly once, in some order.
The permutations may come in any order (the numbers inside each one, of course, may not).
Example 1
- Input
- nums = [2, 5, 8]
- Output
- [[2, 5, 8], [2, 8, 5], [5, 2, 8], [5, 8, 2], [8, 2, 5], [8, 5, 2]]
Example 2
- Input
- nums = [-1, 4]
- Output
- [[-1, 4], [4, -1]]
Constraints
numsholds 1 to 6 numbers.- Every number is between −10 and 10, and no number appears twice.
Show the pattern
Backtracking
An ordering is built one position at a time from the numbers not used yet. Backtracking picks an unused number, fills the remaining positions, then puts the number back to try the next one.
See backtracking in a visualiserShow the approach
Backtrack, filling positions from left to right. Keep the ordering built so far in chosen, and a
used flag for each index of nums.
- When
chosenholds every number, save a copy of it. - Otherwise, for each index not used yet: mark it, append its number, recurse, then pop the number and unmark the index so the next choice can be tried.
There are n choices for the first place, n − 1 for the next, and so on: n! permutations, each
copied in O(n). Leave nums itself unchanged and build the answer in your own lists.
Time: O(n · n!) · Space: O(n) besides the output