46. Permutations - Explanation

Problem Link

Description

Given an array nums of unique integers, return all the possible permutations. You may 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 = [7]

Output: [[7]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10


Recommended Time & Space Complexity

You should aim for a solution with O(n * n!) time and O(n) space, where n is the size of the input array.


Hint 1

A permutation is the same as the array but with the numbers arranged in a different order. The given array itself is also considered a permutation. This means we should make a decision at each step to take any element from the array that has not been chosen previously. By doing this recursively, we can generate all permutations. How do you implement it?


Hint 2

We can use backtracking to explore all possible permutation paths. We initialize a temporary list to append the chosen elements and a boolean array of size n (the same size as the input array) to track which elements have been picked so far (true means the element is chosen; otherwise, false). At each step of recursion, we iterate through the entire array, picking elements that have not been chosen previously, and proceed further along that path. Can you think of the base condition to terminate the current recursive path?


Hint 3

We observe that every permutation has the same size as the input array. Therefore, we can append a copy of the list of chosen elements in the current path to the result list if the size of the list equals the size of the input array terminating the current recursive path.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 0:
            return [[]]

        perms = self.permute(nums[1:])
        res = []
        for p in perms:
            for i in range(len(p) + 1):
                p_copy = p.copy()
                p_copy.insert(i, nums[0])
                res.append(p_copy)
        return res

Time & Space Complexity

  • Time complexity: O(n!∗n2)O(n! * n ^ 2)
  • Space complexity: O(n!∗n)O(n! * n) for the output list.

2. Iteration

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

Time & Space Complexity

  • Time complexity: O(n!∗n2)O(n! * n ^ 2)
  • Space complexity: O(n!∗n)O(n! * n) for the output list.

3. Backtracking

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack([], nums, [False] * len(nums))
        return self.res

    def backtrack(self, perm: List[int], nums: List[int], pick: List[bool]):
        if len(perm) == len(nums):
            self.res.append(perm[:])
            return
        for i in range(len(nums)):
            if not pick[i]:
                perm.append(nums[i])
                pick[i] = True
                self.backtrack(perm, nums, pick)
                perm.pop()
                pick[i] = False

Time & Space Complexity

  • Time complexity: O(n!∗n)O(n! * n)
  • Space complexity: O(n!∗n)O(n! * n) for the output list.

4. Backtracking (Bit Mask)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack([], nums, 0)
        return self.res

    def backtrack(self, perm: List[int], nums: List[int], mask: int):
        if len(perm) == len(nums):
            self.res.append(perm[:])
            return
        for i in range(len(nums)):
            if not (mask & (1 << i)):
                perm.append(nums[i])
                self.backtrack(perm, nums, mask | (1 << i))
                perm.pop()

Time & Space Complexity

  • Time complexity: O(n!∗n)O(n! * n)
  • Space complexity: O(n!∗n)O(n! * n) for the output list.

5. Backtracking (Optimal)

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        self.backtrack(nums, 0)
        return self.res

    def backtrack(self, nums: List[int], idx: int):
        if idx == len(nums):
            self.res.append(nums[:])
            return
        for i in range(idx, len(nums)):
            nums[idx], nums[i] = nums[i], nums[idx]
            self.backtrack(nums, idx + 1)
            nums[idx], nums[i] = nums[i], nums[idx]

Time & Space Complexity

  • Time complexity: O(n!∗n)O(n! * n)
  • Space complexity: O(n!∗n)O(n! * n) for the output list.