Permutations Leetcode Problem 46 [Python Solution]

If you’ve been looking for a problem that combines math and coding, you’re on to the right one with Permutations Leetcode Problem.

In this blog post, we’re going to explore LeetCode Problem 46 – Permutations.

This is a medium difficulty problem falling under the category of backtracking.

Before we dive into the code, don’t forget to hit that like button to support our our platform.

Problem Overview

The problem statement is as follows:

Question: Given an array nums of distinct integers, your task is to return all possible permutations.

The order of the permutations doesn’t matter.

Let’s take a look at a few examples to understand the problem better.

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 integers in nums are unique.

Now, let’s tackle this problem step by step.

Understanding Permutations

Before we dive into the code, let’s understand the concept of permutations.

A permutation is an ordered arrangement of a set of elements.

In this case, the elements are the integers in the nums array.

The order of the elements matters, but we need to find all possible permutations.

The number of permutations you can generate from a set of distinct elements can be calculated using the factorial of the number of elements.

For example, if you have three distinct elements, you can create 3! (3 factorial) permutations, which is equal to 6.

3! = 3 x 2 x 1 = 6

So, the task is to generate all these permutations.

This might seem daunting, but we’ll break it down step by step.

Permutations LeetCode Problem Solution

Let’s start by defining our Python solution for this problem.

We’ll implement a backtracking algorithm to find all permutations.

The algorithm works by systematically exploring all possible choices and then undoing those choices when necessary.

Bruteforce Approach

Our brute-force approach involves recursively generating permutations.

We’ll take the first element from the input array, remove it, and then recursively generate permutations for the remaining elements.

After that, we’ll insert the removed element at all possible positions in the generated permutations.

Here’s the Python code for the brute-force approach:

def permute(self, nums):
    res = []

    # Base case
    if len(nums) == 1:
        return [nums[:]]  # nums[:] is a deep copy

    for i in range(len(nums)):
        n = nums.pop(0)
        perms = self.permute(nums)

        for perm in perms:
            perm.append(n)
        res.extend(perms)
        nums.append(n)
    return res

In this code:

We start with an empty result list, res, to store the permutations.
We define a base case: if the length of nums is 1, we return a list containing nums as the only element.

This is because there’s only one permutation for a single element.

We iterate through the elements in nums and pop the first element, n, to process it.
We recursively call the permute function on the remaining elements in nums, which gives us permutations of the smaller list.
For each permutation in perms, we append n to it, as it can be placed at different positions.
We extend our result list res with these permutations.
Finally, we add n back to the end of nums for the next iteration.

This algorithm generates all permutations for the given input array.

However, it’s not the most efficient solution.

Let’s explore a more efficient approach.

An Efficient Approach with Backtracking

While the brute-force approach works, it involves a lot of unnecessary computation, especially when dealing with larger input arrays.

We can optimize the solution using a backtracking approach.

Here’s an efficient Python solution:

View on GitHub ➹

def permute(self, nums: List[int]) -> List[List[int]]:
    def backtrack(first=0):
        if first == len(nums):
            res.append(nums[:])
        for i in range(first, len(nums)):
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]  # Backtrack

    res = []
    backtrack()
    return res

In this code:

We define a helper function backtrack that takes an optional argument first (default is 0). first represents the current position that we’re considering for swapping.
The base case for our backtracking approach is when first equals the length of nums, indicating that we have successfully generated a permutation.
We use a for loop to consider all possible elements that can be placed at position first.

This eliminates the need for popping and appending elements as in the brute-force approach.

Inside the loop, we swap the elements at positions first and i, effectively placing a different element at position first.

This simulates making a choice.

We then recursively call backtrack with first + 1 to move on to the next position.
After the recursive call, we swap the elements back to their original positions.

This is essential for backtracking, as it allows us to explore different possibilities without modifying the original array.

The res list stores the generated permutations, and we return it as the final result.

This efficient approach reduces unnecessary computations and is faster than the brute-force method.

Time and Space Complexity

Now, let’s analyze the time and space complexity of our efficient approach.

Time Complexity: The time complexity for generating all permutations is O(N!), where N is the number of elements in the input array.

This is because we have to explore all possible orderings of the elements.

Space Complexity: The space complexity is O(N), where N is the number of elements in the input array.

This is due to the space required for the recursion stack and the res list to store the permutations.

Reasoning Behind Our Approach

The reasoning behind our approach is to systematically explore all possible permutations of the given input array.

We use a backtracking algorithm to make choices, explore different paths, and backtrack when necessary.

We start with an empty result list and a helper function, backtrack.
The base case of the backtrack function is when we have successfully generated a permutation (i.e., first reaches the length of the input array).
We use a for loop to consider all possible elements for the current position.
We swap elements to simulate different choices, then make a recursive call and move on to the next position.
After the recursive call, we swap elements back to their original positions (backtrack).
This process continues until all permutations are generated

, and they are added to the res list.

By using this efficient backtracking approach, we avoid unnecessary computations and achieve a faster solution for finding permutations.

Conclusion

In this blog post, we explored the LeetCode Problem 46 – Permutations.

We discussed the problem statement, provided both a brute-force and an efficient backtracking solution in Python, and analyzed the time and space complexity of our approach.

This problem is a great example of how you can apply backtracking to solve a mathematical problem involving permutations.

By systematically exploring all possibilities and using recursion to make and undo choices, we can efficiently generate all permutations.

If you found this guide helpful or have any questions, suggestions, or comments, feel free to share your thoughts below.

Don’t forget to like and engage to support the our platform, and happy coding!

Question Link: Permutations LeetCode Problem