46. Permutations
On This Page
Given an array nums of distinct integers, return all the possible permutations. You can return the answer 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]]
Example 3:
Input: nums = [1]
Output: [[1]]
Idea:
- Draw a decigion tree
- Fix when branch is ready to return
Implementation:
- Recursive:
- Go through every value in
nums - Pop value
- call
perm()with updatednums - from each call(step) append ‘poped’ value from step 2
- Go through every value in
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result_permutation = []
if len(nums) == 1: # base case
return [nums[:]]
for _ in nums:
tmp_removed = nums.pop(0) # remove current element before next step
permutations = self.permute(nums)
for perm in permutations:
perm.append(tmp_removed)
nums.append(tmp_removed)
result_permutation.extend(permutations)
return result_permutation
