46. Permutations

Updated: 2023-03-04

LeetCode problem

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:

1. Draw a decigion tree
2. Fix when branch is ready to return

Implementation:

1. Recursive:
1. Go through every value in nums
2. Pop value
3. call perm() with updated nums
4. from each call(step) append ‘poped’ value from step 2
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