Given an array nums of distinct integers, return every possible ordering (permutation) of its elements. You may return the permutations in any order.
Example 1
Input: 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
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All values are distinct
Hints
Frequently asked at: Amazon, Microsoft, Google, LinkedIn
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
There are n! permutations and each has length n, so O(n * n!) is unavoidable; the work is generating them without repeats or misses. Think of filling n slots from left to right. For each slot we may place any element not used yet. Backtracking explores each choice, goes deeper to fill the next slot, and then undoes the choice so the next candidate can take that slot. A boolean used array makes "is it free?" an O(1) check.
Algorithm
- Create
res, an emptypathand ausedarray of sizen. - If
pathhas lengthn, add a copy toresand return. - For each index
inot yet used: mark it, appendnums[i], recurse. - After the call, pop
nums[i]and unmark it. - Start the recursion and return
res.
Time:
O(n * n!)Space: O(n) for recursion and `used`, plus the outputInterview tip: A swap based version avoids the
used array: swap nums[start] with each nums[i] for i >= start, recurse on start + 1, and swap back. Interviewers may also ask for the next permutation in lexicographic order, which is a different problem (Next Permutation).class Solution: def permute(self, nums: List[int]) -> List[List[int]]: n = len(nums) res, path = [], [] used = [False] * nΒ def backtrack(): if len(path) == n: res.append(path[:]) # a full permutation return for i in range(n): if used[i]: continue used[i] = True # choose path.append(nums[i]) backtrack() # explore path.pop() # un-choose used[i] = FalseΒ backtrack() return resCtrl + Enter runs the examples