Permutations - Leetcode Solution

Problem Statement:

The problem asks us to find all possible permutations of a given array of distinct integers. For example, given the input array [1, 2, 3], the output should be:

[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

Approach:

There are multiple ways to solve this problem, but the most common and simplest ones involve recursion or backtracking.

The basic idea is to fix the first element of the array and recursively generate all possible permutations of the remaining elements. Then move to the second element and repeat the same process until all elements have been fixed as the starting element.

Let's take an example to understand the approach better:

Suppose we have the following input array [1, 2, 3]. We can start by fixing the first element, which can be 1, 2, or 3. Suppose we fix 1 as the first element. Now, we need to find all possible permutations of the remaining elements [2, 3]. To do this, we can again fix the first element as 2 and recursively find all possible permutations of [3]. This will lead to the permutation [1, 2, 3]. Then, we can fix the first element as 3 and recursively find all possible permutations of [2]. This will lead to the permutation [1, 3, 2].

We repeat the same process for the remaining possible starting elements, which are 2 and 3. For the starting element 2, we fix it and recursively find permutations of [1, 3]. This will lead to the permutations [2, 1, 3] and [2, 3, 1]. Similarly, for the starting element 3, we fix it and recursively find permutations of [1, 2], which will lead to the permutations [3, 1, 2] and [3, 2, 1].

So, we need a recursive function that takes the starting element as an argument and generates all possible permutations of the remaining elements. We can use a loop to iterate through all possible starting elements and call the recursive function for each of them. We also need a base case to stop the recursion if we have reached the end of the input array.

Code:

Here's the Python code to solve the problem using recursion:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.permuteHelper(nums, [], res)
        return res
    
    def permuteHelper(self, nums, curr, res):
        if not nums:
            res.append(curr)
        for i in range(len(nums)):
            self.permuteHelper(nums[:i] + nums[i+1:], curr + [nums[i]], res)

The permute() function takes the input array as an argument and returns the list of all possible permutations. It initializes an empty list to store the permutations and calls the permuteHelper() function, which takes three arguments: the remaining elements (nums), the current permutation (curr), and the list to store all permutations (res).

The permuteHelper() function first checks if there are no remaining elements in nums. If so, it means we have found one possible permutation, so we add the current permutation to res.

If there are remaining elements, we loop through them and recursively call the permuteHelper() function with the remaining elements (nums[:i] + nums[i+1:]), the current permutation with the current element added (curr + [nums[i]]), and res.

The loop ensures that we generate all possible permutations by trying all possible starting elements. The recursive call generates all possible permutations of the remaining elements.

Time Complexity:

The time complexity of this approach is O(n!), as there are n! possible permutations of n distinct elements.

Space Complexity:

The space complexity of this approach is also O(n!), as we need to store all n! permutations in the result list. The recursive stack also consumes O(n) space.

1