Permutations Solution for Microsoft

Company: Microsoft · Difficulty: Medium · Topics: Array, Backtracking

Problem Statement

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

A permutation is an arrangement of all the elements of a set in a specific 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]]

Explanation:

All possible permutations of [1,2,3] are:

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

Explanation:

All possible permutations of [0,1] are:

[0,1], [1,0]

Example 3:

Input: nums = [1]

Output: [[1]]

Explanation:

Only one element, so only one permutation.

Example 4:

Input: nums = [1,2,3,4]

Output: [[1,2,3,4],[1,2,4,3],[1,3,2,4],[1,3,4,2],[1,4,2,3],[1,4,3,2],[2,1,3,4],[2,1,4,3],[2,3,1,4],[2,3,4,1],[2,4,1,3],[2,4,3,1],[3,1,2,4],[3,1,4,2],[3,2,1,4],[3,2,4,1],[3,4,1,2],[3,4,2,1],[4,1,2,3],[4,1,3,2],[4,2,1,3],[4,2,3,1],[4,3,1,2],[4,3,2,1]]

Intuition

The key insight is to use backtracking (recursion) to generate all possible permutations. For each position in the permutation, we need to try all available numbers that haven't been used yet.

This is essentially generating all possible arrangements of the given numbers, where each number appears exactly once in each permutation.

Approach

Approach 1: Backtracking (Optimal)

1. Use recursion to build permutations

2. For each position, try all unused numbers

3. Mark numbers as used when placed

4. When permutation is complete, add to result

5. Backtrack by unmarking numbers

Approach 2: Iterative with Next Permutation

1. Sort the array first

2. Generate next permutation using algorithm

3. Continue until all permutations are generated

4. Add each permutation to result

Approach 3: Recursive with Swapping

1. Use recursion with array swapping

2. Swap elements to generate different arrangements

3. When reaching the end, add current arrangement

4. Backtrack by swapping back

Dry Run

Let's trace through Example 1: nums = [1,2,3]

Backtracking Approach:

Initialize: used = [false, false, false], current = []
Position 0:
Try 1: used[0] = true, current = [1]
Position 1:
Try 2: used[1] = true, current = [1,2]
Position 2:
Try 3: used[2] = true, current = [1,2,3] → add to result
used[2] = false
used[1] = false
Try 3: used[2] = true, current = [1,3]
Position 2:
Try 2: used[1] = true, current = [1,3,2] → add to result
used[1] = false
used[2] = false
used[0] = false
Try 2: used[1] = true, current = [2]
Continue similar process...
Result: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Key Insights

1. Backtracking: Perfect for generating all permutations

2. Used Array: Track which numbers have been used in current permutation

3. Base Case: When current permutation length equals input array length

4. State Management: Keep track of current permutation being built

Edge Cases

1. Single Element: Return [[element]]

2. Two Elements: Return both arrangements

3. Empty Array: Return empty array

4. Large Arrays: Handle factorial growth efficiently

Solutions

Best Approach: Backtracking

Time Complexity: O(n!) where n is the number of elements
Space Complexity: O(n) for recursion stack
Key Idea: Use recursion to generate all permutations

Average Approach: Next Permutation

Time Complexity: O(n!)
Space Complexity: O(n)
Key Idea: Generate permutations iteratively

Worst Approach: Recursive with Swapping

Time Complexity: O(n!)
Space Complexity: O(n)
Key Idea: Use array swapping for permutations