196.md

46. Permutations

Difficulty: 🟡 Medium

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Examples:

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.

Solutions

O(n!) solution

Python3

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

        permutations = []
        for i in range(size):
            num = nums[i]
            remaining_nums = nums[:i] + nums[i+1:]

            for permutation in self.permute(remaining_nums):
                permutations.append([num]+permutation)

        return permutations

The provided solution uses a recursive approach to generate all possible permutations of the input array nums. The key idea is to select one element from the array as the first element of each permutation and recursively generate permutations for the remaining elements. The base case occurs when the array has only one element, in which case the array itself is a valid permutation.

Here's a step-by-step explanation of the solution:

1. Initialize a variable size to store the length of the input array nums.

2. Check if the value of size is equal to 1. If size is 1, it means there is only one element in the array, so return a list containing the array itself as the only permutation. This serves as the base case for the recursion.

3. If size is greater than 1, create an empty list permutations to store the permutations.

4. Iterate through the elements of the nums array using a loop variable i from 0 to size-1. For each element at index i, do the following:

   • Extract the element num at index i.
   • Create a new list remaining_nums that contains all elements of nums except the one at index i. This is done using list slicing.
   • Recursively call the permute function with the remaining_nums array to generate permutations for the remaining elements. The result is a list of lists representing permutations of the remaining elements.

5. For each generated permutation of the remaining elements, append the num element (selected in step 4) as the first element of the permutation. This creates a new permutation with num as the first element.

6. Repeat step 5 for all elements in the nums array, generating permutations for each possible starting element.

7. After the loop completes, the permutations list will contain all possible permutations of the nums array.

8. Return the permutations list as the final result.

Complexity Analysis

• Time Complexity: The solution generates all possible permutations of the input array nums. The number of permutations is equal to n!, where n is the length of the array. Therefore, the time complexity is O(n!), where n is at most 6 (as given in the problem constraints). As the input size is small (n <= 6), the time complexity is manageable.

• Space Complexity: The solution uses a constant amount of extra space for variables, and the space required for the permutations list is proportional to the number of permutations generated. Since there are n! permutations, the space complexity is O(n!) in the worst case.

Summary

The provided solution effectively generates all possible permutations of the input array nums using a recursive approach. It recursively selects one element as the first element of each permutation and generates permutations for the remaining elements. The base case is when there is only one element, in which case the array itself is returned as a permutation. The solution handles small input sizes efficiently.

NB: If you want to get community points please suggest solutions in other languages as merge requests.