NUHMAN.com

Introduction

LeetCode 46: Permutations is a problem where you're tasked with generating all possible permutations of a given list of numbers. This is a classic backtracking problem where we explore all possible arrangements of elements while adhering to constraints (in this case, the elements should not be repeated within each permutation).

The problem is typically solved efficiently using a backtracking approach to generate each possible permutation recursively.

Problem Statement

Given a collection of distinct integers, return all possible permutations of the numbers. You can assume that the input array will have no duplicate numbers.

Example 1:

go

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:

go

Input: nums = [0,1]
Output:
[
  [0,1],
  [1,0]
]

Approach: Backtracking

We can generate all the permutations of the input array nums by recursively building the permutations. At each step:

1. Swap each element into the current position.
2. Recursively generate all permutations for the remaining elements.
3. Swap back to restore the array for the next iteration.

The algorithm continues this process until all permutations are generated.

Steps:

1. Backtracking: At each index, swap elements and recursively generate permutations of the subarray.
2. Swap and Restore: After the recursion, swap back to restore the original order of the array.
3. Base Case: If all elements have been fixed (i.e., we have used all elements), record the current permutation.

Go Implementation

go

func permute(nums []int) [][]int {
    var res [][]int
    backtrack(nums, 0, &res)
    return res
}

func backtrack(nums []int, start int, res *[][]int) {
    // If all elements are fixed, add the permutation to the result
    if start == len(nums) {
        // Create a copy of the current permutation and append it to result
        temp := make([]int, len(nums))
        copy(temp, nums)
        *res = append(*res, temp)
        return
    }

    // Generate permutations by swapping each element into the 'start' position
    for i := start; i < len(nums); i++ {
        // Swap the current element with the element at the 'start' position
        nums[start], nums[i] = nums[i], nums[start]

        // Recursively generate permutations for the next position
        backtrack(nums, start+1, res)

        // Backtrack and swap the elements back
        nums[start], nums[i] = nums[i], nums[start]
    }
}

Example Walkthrough

Example 1:

go

Input: nums = [1,2,3]

1. Initial Call: backtrack([1, 2, 3], 0, res)

• Start at index 0, swap 1 with 1 (no change).
• Call recursively for index 1: backtrack([1, 2, 3], 1, res)
• Swap 2 with 2 (no change), call for index 2: backtrack([1, 2, 3], 2, res)
• Swap 3 with 3 (no change), call for index 3 (base case reached).
• Record permutation: [1, 2, 3].
• Backtrack: Swap 3 with 3 again (no change).
• Swap 3 with 2, call for index 2: backtrack([1, 3, 2], 2, res)
• Swap 2 with 2, call for index 3.
• Record permutation: [1, 3, 2].
• Continue backtracking for other permutations.

1. Final Output:

go

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

Time and Space Complexity

MetricComplexityTime ComplexityO(n!)Space ComplexityO(n)

• Time Complexity: The number of permutations of n distinct elements is n!. Since we need to generate all permutations and store them, the time complexity is O(n!).
• Space Complexity: The space complexity is O(n) due to the recursion depth (which is n) and the space required to store the result.

Edge Cases

• Single Element: A single-element array has only one permutation.
• Input: [1]
• Output: [[1]]
• Empty Array: An empty array has only one permutation, which is the empty array itself.
• Input: []
• Output: [[]]
• Two Elements: An array with two elements has exactly two permutations.
• Input: [1, 2]
• Output: [[1, 2], [2, 1]]

Key Takeaways

• Backtracking is an ideal approach for problems that involve generating all possible combinations or permutations, as it allows us to explore each option while ensuring constraints are met.
• The solution is efficient with respect to the number of permutations generated, but its time complexity is O(n!), which grows rapidly as the number of elements increases.
• The recursive backtracking approach ensures that we generate all permutations systematically, handling each element's position one at a time.