Permutations

Permutations show up all the time in coding interviews, specifically by MAANG (Meta, Google, Microsoft, Amazon, and Apple). This is because they test two core skills at once: exploring a search space systematically and keeping your solution correct under lots of branching choices. In this problem, you’re asked to generate every ordering of a set of distinct integers, which is a classic setup for recursion and backtracking.

Interviewers like it because the brute force idea is easy to say, but the real challenge is implementing it cleanly without duplicates, missed cases, or messy extra data structures. If you can solve permutations confidently, you’re also building the same mindset you’ll use for subsets, combinations, and many “try all possibilities” problems.

Problem statement

You’re given an array nums of distinct integers. Return all the possible permutations of those integers, in any order.

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Examples

How permutation works?

If we recall the classic idea of permutations, they are formed by making a sequence of choices. For an array of n distinct numbers, the first position can be filled in n different ways. After we place one number, it can’t be used again in the same arrangement, so the second position has n−1 remaining choices, then n−2, and so on until only one number is left. This is exactly why there are n! total permutations.

n × (n−1) × (n−2) × ⋯ × 1 = n!

Optimized solution using Backtracking

To solve the permutation problem, think of it as building the answer one position at a time from left to right. At each step, you decide which number should go in the current position, and once that choice is made, you move forward to arrange the remaining positions using the remaining numbers. This approach mirrors the exact counting logic behind permutations and avoids inefficient strategies like randomly shuffling or generating extra results and filtering them later.

A clean and efficient way to implement this idea is backtracking with in-place swapping. When you are at index i, you treat it as the position you are currently fixing. You try every possible number for that position by swapping nums[i] with each element from index i onward. Each swap brings a different number into the current position while keeping the rest of the numbers available for future positions. After performing the swap, you recurse to fill the next index. When the recursion reaches the end of the array, the current arrangement is a complete permutation, so you store a copy of it. Then you undo the swap to restore the array to its previous state before trying the next option. This repeated “choose, explore, undo” process is the essence of backtracking and, when the input elements are distinct, it generates every valid permutation exactly once.

Algorithm steps

1. Make an empty list result to store all permutations, and set n as the length of nums.
2. Start recursion with backtrack(first = 0), where first means the index we are currently fixing. Inside backtrack:
   1. If first == n, it means every position is fixed, so copy the current nums and add it to result.
   2. Otherwise, for every index i from first to n-1, try placing nums[i] into position first.
      1. Swap nums[first] and nums[i] to bring a new number into the current fixed position.
      2. Call backtrack(first + 1) to move to the next index and decide which number should be placed there, using the remaining unfixed numbers.
      3. Swap back nums[first] and nums[i] to restore the array before trying the next i.
3. When all choices are explored, return result, which now contains every permutation.

The slides below will help you better understand the solution.

1 / 13

Python code for the optimized solution

Here’s the Python code for the optimized solution using backtracking and in-place swapping.

def permute(nums):
    result = []
    n = len(nums)

    def backtrack(first):
        # Base case: if we've fixed positions [0..n-1], we formed one permutation
        if first == n:
            result.append(nums[:])  # copy current arrangement
            return

        # Try putting each remaining number into position `first`
        for i in range(first, n):
            # Choose: swap current number into the "first" position
            nums[first], nums[i] = nums[i], nums[first]

            # Explore: fix the next position
            backtrack(first + 1)

            # Un-choose: swap back to resulttore original order (backtrack)
            nums[first], nums[i] = nums[i], nums[first]

    # Start fixing from index 0
    backtrack(0)
    return result


# Driver code
def main():
    test_cases = [
        [5, 6, 7],
        [3, 8],
        [-6, 0, 2],
        [5],
    ]

    for i, nums in enumerate(test_cases, 1):
        resultult = permute(nums[:])  # pass a copy so original test case stays unchanged
        print(f"{i}.\tnums = {nums}")
        print(f"\n\tOutput: {resultult}")
        print("-" * 75)

if __name__ == "__main__":
    main()

Time complexity

The algorithm produces every possible permutation, and for n distinct numbers there are n! different permutations. That already means we must do work proportional to n!, because we can’t output fewer than that.

Additionally, to store each permutation we create a copy of the whole list. Copying a list of length n takes O(n) time. As this copy happens once for each of the n! permutations, the total copying cost is:

• O(n) work per permutation
• repeated n! times

So, the overall time complexity becomes O(n × n!).

Space complexity

The auxiliary space complexity is O(n) (excluding the output list) because the recursion can go as deep as n calls and the algorithm only uses a constant amount of extra space besides that.

Common mistakes to avoid

Keep an eye for these common mistakes:

• Modifying the input without restoring it: The core of backtracking is explore and return. If you swap two elements or mark a number as used, you must undo that action after the recursive call. Failing to un-swap or un-mark will corrupt the state for the next branch of the recursion tree, leading to missing or incorrect results.
• Miscalculating time complexity: Do not simply say the time complexity is O(n!). While there are n! permutations, you perform work at each step. Specifically, when you reach the base case, copying an array of size n into your results takes O(n) time. Therefore, the total time complexity is O(n x n!).
• Neglecting the recursion stack in space complexity: When asked about space complexity, candidates often forget the call stack. Even if you use an in-place swapping method (which uses O(1) extra auxiliary space for the array itself), the recursion depth is n. Therefore, the space complexity is O(n) due to the stack frames.