LC 46 - Permutations

Question

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]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Links

Question here and solution here

Solution

concept

This question is different from 78. Subsets because we want to get all permutation and only the full elements. We can use standard backtrack like in the previous questions but alot of book keeping is needed. The main idea is to phrase the sub problem such that we only look at nums[1:] each time, i.e. do not care about the first element.

1. the subproblem is how do I create permutation from the rest of the array
2. we then notice that we just need to insert the first element nums[0] at all possible index to get all permutations.

code

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return [[]]
        
        perms = self.permute(nums[1:])
        ans = []
        for p in perms:
            for i in range(len(p) + 1):
                p_copy = p.copy()
                p_copy.insert(i, nums[0])
                ans.append(p_copy)

        return ans
        
class Solution:
	"""
	same but different format
	"""
    def permute(self, nums: List[int]) -> List[List[int]]:

        def dfs(arr):
            if len(arr) == 0:
                return [[]]
            
            perms = dfs(arr[1:])
            ans = []
            for p in perms:
                for i in range(len(p)+1):
                    p_copy = p.copy()
                    p_copy.insert(i, arr[0])
                    ans.append(p_copy)

            return ans
        
        return dfs(nums)

Complexity

time: $O(n! * n^2)$
space: $O(n! * n)$