🔀46. Permutations
Medium | Grind 75 | Wednesday August 3, 2022
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]SOLUTION
The question is asking us for all the permutation of the list without repeating the elements. The total number of permutations or possible combinations is n! where n is the number of elements. Let's look at example 1. Before even solving the question, we know there has to be 6 unique list as our answer because 3! = 6. The answer is 3! because every combination needs 3 elements. _ _ _. There are 3 possibilities for the first dash since we have 3 elements. Next dash, there will be only 2 since we used up one before. And in the end we will have one possible element. Therefore, in total, we have 3 x 2 x 1 possible combinations.
In terms of coding, the idea is similar to the above possibilities explanation. Once we take one element, we will remove them from the list and iterate over the new list. We will then take an element from our new list, remove it from our new list and repeat. Whenever we take an element and pop it out of our list, we will add it to another list that will make up the permutation for when you start with the element.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
result = [] # store all the permutations
self.combine(result, nums, [])
return result
def combine(self, result, nums, path):
'''
recursive call to permute and combine different elelments
@param result: list - store list of different permutations.
@param nums: list - list of numbers without the current element we are looking at.
@param path: list - list storing the unique permutation of the current element.
'''
# we have iterated over all possibilities when starting with the current element.
if len(nums) == 0:
result.append(path)
return
else:
# iterate over the elements and recurse with a new list without the current element.
for element in nums:
new_nums = nums[:]
new_nums.remove(element)
self.combine(result, new_nums, path+[element])
Last updated