Permutations medium

Problem Statement

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

Steps to Solve

The core idea is to use backtracking. We'll recursively explore all possible arrangements of the numbers.

1. Base Case: If we've placed all numbers (the current permutation's length equals the input array's length), we've found a permutation; add it to the result.

2. Recursive Step: For each unplaced number:

   • Place the number in the current permutation.
   • Recursively explore permutations with the remaining unplaced numbers.
   • Remove the number from the current permutation (backtracking) to explore other possibilities.

Explanation

The backtracking approach systematically tries all possible arrangements. Imagine a tree where each level represents choosing a number for a position in the permutation. The code explores all branches of this tree. The backtracking function handles the recursive exploration. It keeps track of the currently built permutation (current_permutation) and the numbers that are yet to be used (remaining_numbers).

Code

from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtracking(current_permutation, remaining_numbers):
            if not remaining_numbers:  # Base case: all numbers placed
                result.append(current_permutation.copy())  # Add a copy to avoid modification
                return

            for i in range(len(remaining_numbers)):
                # Choose the i-th number
                next_number = remaining_numbers[i]
                
                # Explore with the number
                current_permutation.append(next_number)
                backtracking(current_permutation, remaining_numbers[:i] + remaining_numbers[i+1:])
                
                # Backtrack: remove the number to explore other choices
                current_permutation.pop()

        backtracking([], nums)  # Start with an empty permutation and all numbers available
        return result

Complexity Analysis

• Time Complexity: O(n * n!), where n is the length of the input array. There are n! permutations, and for each permutation, we spend O(n) time to build and add it to the result.

• Space Complexity: O(n), primarily due to the recursion depth and the space used by current_permutation. The space used by the result list is also O(n * n!), but that's considered output space and not usually included in the space complexity analysis.