Permutations - Solution & Explanation

Problem Overview: Given an array of distinct integers, return all possible permutations of the numbers. Each permutation represents a different ordering of the same elements, and the result must include every possible arrangement.

Approach 1: Backtracking (Time: O(n! * n), Space: O(n))

This problem naturally fits backtracking. You build permutations incrementally by choosing an unused element, adding it to the current path, and recursively exploring further choices. A boolean used[] array or in-place swapping ensures each element appears only once in the current permutation.

The key insight is that every position in the permutation can be filled by any unused element. For each recursive level, iterate through the array, pick an unused number, append it to the current permutation, and recurse. Once the permutation length reaches n, add a copy to the result list. Then backtrack by removing the last element and marking it unused.

This generates exactly n! permutations. Copying each permutation takes O(n), which leads to an overall time complexity of O(n! * n). The recursion depth is O(n), and auxiliary space is mainly the recursion stack and the current permutation. Backtracking is the most common interview solution and heavily relies on concepts from recursion and array traversal.

Approach 2: Iterative Permutation Generation (Time: O(n! * n), Space: O(n!))

An iterative strategy builds permutations progressively. Start with a list containing an empty permutation. For each number in the input array, insert it into every possible position of every existing permutation. If a permutation has length k, inserting the new number produces k + 1 new permutations.

Example: starting with [ ], inserting 1 gives [1]. Inserting 2 into [1] creates [2,1] and [1,2]. Continue inserting the next element into every position of each existing permutation until all numbers are processed.

This approach avoids recursion and can be easier to reason about in iterative environments. However, it repeatedly copies arrays when inserting elements, which increases memory overhead. The total number of generated permutations is still n!, and each insertion operation costs up to O(n), resulting in O(n! * n) time complexity.

Recommended for interviews: Backtracking is the expected approach. It demonstrates control over recursion, state management, and pruning. Interviewers usually want to see the recursive exploration pattern and proper backtracking logic. The iterative insertion approach is useful as an alternative but appears less frequently in coding interviews.