Array arrangement variations

You're sitting in a Meta interview when the interviewer pulls up a shared editor and types out a short array: [1, 2, 3]. "I want you to generate every possible ordering of these numbers," they say. It sounds straightforward, but this problem is testing something deeper: whether you can systematically explore a search space without missing arrangements or producing duplicates. This is the classic permutations problem, also known as "Permutations" on other platforms, and it is one of the most important backtracking problems you will encounter.

TL;DR

Use backtracking to build each permutation one element at a time. At each step, iterate through the input array and skip elements already in the current permutation. When the current permutation reaches the same length as the input, save a copy to the result. After each recursive call, remove the last element to explore other choices. This generates all n! permutations in O(n * n!) time and space.

Why This Problem Matters

Permutations sit at the heart of the backtracking pattern. Once you understand how to systematically build and undo choices in this problem, you have the template for solving dozens of related problems: combinations, subsets, N-Queens, Sudoku, and more. Meta, Bloomberg, and TikTok all ask this problem regularly because it cleanly tests recursive thinking and your ability to manage state across recursive calls.

Understanding the Problem

Given an array of distinct integers, generate all possible permutations. The order in which you return them does not matter, but every unique arrangement must appear exactly once.

For [1, 2, 3], the six permutations are:

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

The constraints are generous: the array has at most 6 elements, so we are dealing with at most 720 permutations. The real challenge is not performance but correctness and clean implementation.

Edge Cases

1. Single element: [1] has exactly one permutation: [[1]]
2. Two elements: [0, 1] yields [[0, 1], [1, 0]]
3. Negative numbers: [-1, 0, 1] works identically since all elements are distinct

The Backtracking Framework

Backtracking is a general algorithm for finding all solutions to a constraint satisfaction problem. It works by incrementally building candidates and abandoning ("backtracking") any candidate that cannot possibly lead to a valid solution.

Every backtracking problem has three components:

1. Choice: What options are available at this step?
2. Constraint: Which options are valid given what we have chosen so far?
3. Goal: When have we built a complete solution?

For permutations:

• Choice: Any element from the input array
• Constraint: The element must not already be in the current permutation
• Goal: The current permutation has the same length as the input

Visualizing the Recursion Tree

The best way to understand backtracking is to draw the recursion tree. Each node represents the state of the current permutation, and each edge represents choosing the next element.

Starting from an empty array at the root, we pick each available number in turn. At level 1, we choose from 3. At level 2, we choose from the remaining numbers. At level 3, there is only one number left, completing the permutation. The six leaves are our six results.

Walking Through One Branch

Let's trace the leftmost branch in detail. We start with an empty permutation and pick 1. Then from the remaining 3, we pick 2. Finally, we pick the only remaining element, 3, giving us [1, 2, 3].

After recording [1, 2, 3], the algorithm backtracks: it removes 3, then removes 2, and tries 3 instead. This produces [1, 3, 2]. The state evolution below shows this backtrack-and-choose pattern:

The highlighted nodes are complete permutations that get added to the result. The "Backtrack" step is where we undo the previous choice and try the next available element.

Implementation

Prefer a different language? Jump to solutions in other languages.

Here is the Java implementation using the backtracking pattern:

import java.util.*;

public class Solution {
  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums);
    return result;
  }

  private void backtrack(List<List<Integer>> result, List<Integer> currentPermutation, int[] nums) {
    if (currentPermutation.size() == nums.length) {
      result.add(new ArrayList<>(currentPermutation));
    } else {
      for (int i = 0; i < nums.length; i++) {
        if (currentPermutation.contains(nums[i])) continue;
        currentPermutation.add(nums[i]);
        backtrack(result, currentPermutation, nums);
        currentPermutation.remove(currentPermutation.size() - 1);
      }
    }
  }
}

Let's walk through the key parts:

1. Base case: When currentPermutation.size() == nums.length, we have built a complete permutation. We add a copy (via new ArrayList<>(currentPermutation)) because the same list object gets modified as we backtrack.

2. The loop: We iterate over every element in nums. The contains check enforces our constraint: skip elements already chosen.

3. Choose: currentPermutation.add(nums[i]) adds the element.

4. Explore: The recursive backtrack call continues building the permutation.

5. Unchoose: currentPermutation.remove(currentPermutation.size() - 1) undoes our choice so the next iteration of the loop can try a different element.

This choose-explore-unchoose pattern is the backbone of every backtracking solution.

Why We Copy the List

A subtle but critical detail: when we find a complete permutation, we must add new ArrayList<>(currentPermutation) rather than currentPermutation itself. Since we reuse the same list object throughout the recursion, adding a direct reference would mean all entries in result point to the same list, which ends up empty after all the backtracking completes.

Complexity Analysis

Time Complexity: O(n * n!)

There are exactly n! permutations of n distinct elements. For each permutation, we spend O(n) time copying it into the result list. The contains check inside the loop also costs O(n) per call, but since each level of recursion runs the loop at most n times and the tree has n levels, the total work across all recursive calls is bounded by O(n * n!).

Space Complexity: O(n * n!)

The result stores n! permutations, each of length n, for O(n * n!) total. The recursion stack goes n levels deep, using O(n) space. The currentPermutation list also uses O(n) space. The output dominates.

Could We Do Better?

No. Any algorithm that generates all permutations must produce n! results of size n, so O(n * n!) is a lower bound on both time and space. The backtracking approach achieves this bound.

Common Pitfalls

1. Forgetting to copy: Adding currentPermutation directly to result instead of making a copy. Every entry ends up pointing to the same (eventually empty) list.

2. Not undoing the choice: Forgetting currentPermutation.remove(...) after the recursive call means elements accumulate and no valid permutation is ever formed.

3. Using a boolean array with wrong indices: Some implementations track used elements with a boolean[] used array. This works well but requires careful index management. The contains approach shown here is simpler for arrays with at most 6 elements.

4. Returning permutations in a specific order: The problem says "any sequence," so don't waste time sorting the output.

The Swap-Based Alternative

There is another popular approach that generates permutations by swapping elements in the input array itself. Instead of maintaining a separate currentPermutation list and checking for duplicates, you fix one element at each position by swapping it into place:

private void backtrackSwap(List<List<Integer>> result, int[] nums, int start) {
    if (start == nums.length) {
        List<Integer> perm = new ArrayList<>();
        for (int num : nums) perm.add(num);
        result.add(perm);
    } else {
        for (int i = start; i < nums.length; i++) {
            swap(nums, start, i);
            backtrackSwap(result, nums, start + 1);
            swap(nums, start, i);  // backtrack
        }
    }
}

This avoids the O(n) contains check per element, making it slightly faster in practice. The Go and Scala solutions below use this swap-based variant.

Interview Tips

When solving this problem in an interview:

1. Draw the recursion tree first. Sketch the tree for [1, 2, 3] on the whiteboard. This shows the interviewer you understand the structure before writing any code.

2. Name the three backtracking components. Explicitly state the choice (pick an unused element), constraint (element not already in current permutation), and goal (permutation length equals input length).

3. Trace through one branch. Walk the interviewer through one complete path from root to leaf and back, showing the backtrack step.

4. Mention the copy. Call out that you are copying the list when adding to results. This is a common source of bugs and shows attention to detail.

5. Discuss the swap variant as a follow-up optimization, especially if the interviewer asks about reducing the overhead of the contains check.

Key Takeaways

• Backtracking generates permutations by systematically choosing, exploring, and unchoosing elements. The recursion tree for n elements has n! leaves, one per permutation.
• Always copy the current permutation before adding it to the result. Reusing the same list object across recursive calls is the most common source of bugs.
• The contains-check approach is clean and simple for small arrays (n ≤ 6). The swap-based approach avoids the linear scan and is preferred for larger inputs.
• This problem is the template for all backtracking problems. The choose-explore-unchoose pattern applies directly to combinations, subsets, N-Queens, and Sudoku.
• Time and space are both O(n * n!), which is optimal since any algorithm must produce all n! permutations.

Related Problems and Practice

Once you are comfortable with basic permutations, try these progressively harder backtracking challenges:

• Permutations with duplicates: Sort the array and skip duplicate elements at the same recursion level
• Combinations / Subsets: Similar backtracking but without requiring all elements
• N-Queens: Backtracking with more complex constraints
• Sudoku Solver: Backtracking with row, column, and box constraints

This problem and hundreds of other backtracking challenges are available on Firecode, where over 50,000 engineers have prepared for technical interviews at companies like Meta, Bloomberg, and TikTok. Consistent practice with the backtracking pattern will make these problems feel routine.

Solutions in Other Languages

Python

class Solution:
    def permute(self, nums):
        result = []
        self._backtrack(result, [], nums)
        return result

    def _backtrack(self, result, current_permutation, nums):
        if len(current_permutation) == len(nums):
            result.append(current_permutation[:])
        else:
            for num in nums:
                if num in current_permutation:
                    continue
                current_permutation.append(num)
                self._backtrack(result, current_permutation, nums)
                current_permutation.pop()

JavaScript

class Solution {
  permute(nums) {
    const result = [];
    const backtrack = (path, options) => {
      if (path.length === nums.length) {
        result.push([...path]);
        return;
      }
      for (let i = 0; i < options.length; i++) {
        path.push(options[i]);
        backtrack(path, options.slice(0, i).concat(options.slice(i + 1)));
        path.pop();
      }
    };
    backtrack([], nums);
    return result;
  }
}

The JavaScript solution takes a slightly different approach: instead of checking contains, it passes a shrinking options array that excludes the chosen element. This avoids the linear scan but creates new arrays on each call.

TypeScript

class Solution {
  permute(nums: number[]): number[][] {
    const result: number[][] = [];
    const backtrack = (path: number[], options: number[]): void => {
      if (path.length === nums.length) {
        result.push([...path]);
        return;
      }
      for (let i = 0; i < options.length; i++) {
        path.push(options[i]);
        backtrack(path, options.slice(0, i).concat(options.slice(i + 1)));
        path.pop();
      }
    };
    backtrack([], nums);
    return result;
  }
}

C++

#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> permute(std::vector<int> &nums) {
    std::vector<std::vector<int>> result;
    std::vector<int> current;
    std::vector<bool> used(nums.size(), false);
    backtrack(nums, used, current, result);
    return result;
  }

private:
  void backtrack(const std::vector<int> &nums, std::vector<bool> &used,
                 std::vector<int> &current, std::vector<std::vector<int>> &result) {
    if (current.size() == nums.size()) {
      result.push_back(current);
      return;
    }
    for (size_t i = 0; i < nums.size(); ++i) {
      if (used[i]) continue;
      used[i] = true;
      current.push_back(nums[i]);
      backtrack(nums, used, current, result);
      current.pop_back();
      used[i] = false;
    }
  }
};

The C++ solution uses a boolean vector to track which elements are in use, avoiding the O(n) contains check per element.

Go

The Go solution uses the swap-based approach, generating permutations by swapping elements into position rather than maintaining a separate list.

func Permute(nums []int) [][]int {
    var result [][]int
    var backtrack func(first int)
    backtrack = func(first int) {
        if first == len(nums) {
            perm := make([]int, len(nums))
            copy(perm, nums)
            result = append(result, perm)
            return
        }
        for i := first; i < len(nums); i++ {
            nums[first], nums[i] = nums[i], nums[first]
            backtrack(first + 1)
            nums[first], nums[i] = nums[i], nums[first]
        }
    }
    backtrack(0)
    return result
}

Scala

Scala also uses the swap-based approach with a mutable buffer for collecting results.

class Solution {
  def permute(nums: Array[Int]): List[List[Int]] = {
    def backtrack(start: Int, end: Int, current: Array[Int],
                  result: scala.collection.mutable.ListBuffer[List[Int]]): Unit = {
      if (start == end) {
        result += current.toList
      } else {
        for (i <- start until end) {
          swap(current, start, i)
          backtrack(start + 1, end, current, result)
          swap(current, start, i)
        }
      }
    }

    def swap(arr: Array[Int], i: Int, j: Int): Unit = {
      val temp = arr(i)
      arr(i) = arr(j)
      arr(j) = temp
    }

    val result = scala.collection.mutable.ListBuffer[List[Int]]()
    backtrack(0, nums.length, nums.clone(), result)
    result.toList
  }
}

Kotlin

class Solution {
  fun permute(nums: IntArray): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    backtrack(result, mutableListOf(), nums)
    return result
  }

  private fun backtrack(result: MutableList<List<Int>>,
                        currentPermutation: MutableList<Int>, nums: IntArray) {
    if (currentPermutation.size == nums.size) {
      result.add(currentPermutation.toList())
    } else {
      for (i in nums.indices) {
        if (nums[i] in currentPermutation) continue
        currentPermutation.add(nums[i])
        backtrack(result, currentPermutation, nums)
        currentPermutation.removeAt(currentPermutation.size - 1)
      }
    }
  }
}

Rust

impl Solution {
    pub fn permute(&self, nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        Self::backtrack(&mut result, &mut Vec::new(), &nums);
        result
    }

    fn backtrack(result: &mut Vec<Vec<i32>>, current: &mut Vec<i32>, nums: &[i32]) {
        if current.len() == nums.len() {
            result.push(current.clone());
        } else {
            for i in 0..nums.len() {
                if current.contains(&nums[i]) { continue; }
                current.push(nums[i]);
                Self::backtrack(result, current, nums);
                current.pop();
            }
        }
    }
}

Swift

class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var result: [[Int]] = []
        backtrack(&result, [], nums)
        return result
    }

    private func backtrack(_ result: inout [[Int]], _ currentPermutation: [Int], _ nums: [Int]) {
        if currentPermutation.count == nums.count {
            result.append(currentPermutation)
        } else {
            for i in 0..<nums.count {
                if currentPermutation.contains(nums[i]) { continue }
                var currentPermutation = currentPermutation
                currentPermutation.append(nums[i])
                backtrack(&result, currentPermutation, nums)
            }
        }
    }
}

Ruby

class Solution
  def permute(nums)
    result = []
    backtrack(result, [], nums)
    result
  end

  private

  def backtrack(result, current_permutation, nums)
    if current_permutation.length == nums.length
      result << current_permutation.dup
    else
      nums.each do |num|
        next if current_permutation.include?(num)
        current_permutation << num
        backtrack(result, current_permutation, nums)
        current_permutation.pop
      end
    end
  end
end

Dart

class Solution {
  List<List<int>> permute(List<int> nums) {
    List<List<int>> result = [];
    backtrack(result, [], nums);
    return result;
  }

  void backtrack(List<List<int>> result, List<int> currentPermutation, List<int> nums) {
    if (currentPermutation.length == nums.length) {
      result.add(List.from(currentPermutation));
    } else {
      for (int i = 0; i < nums.length; i++) {
        if (currentPermutation.contains(nums[i])) continue;
        currentPermutation.add(nums[i]);
        backtrack(result, currentPermutation, nums);
        currentPermutation.removeLast();
      }
    }
  }
}

PHP

class Solution {
    public function permute(array $nums): array {
        $result = [];
        $this->backtrack($result, [], $nums);
        return $result;
    }

    private function backtrack(array &$result, array $currentPermutation, array $nums): void {
        if (count($currentPermutation) === count($nums)) {
            $result[] = $currentPermutation;
        } else {
            for ($i = 0; $i < count($nums); $i++) {
                if (in_array($nums[$i], $currentPermutation)) continue;
                $currentPermutation[] = $nums[$i];
                $this->backtrack($result, $currentPermutation, $nums);
                array_pop($currentPermutation);
            }
        }
    }
}

C#

using System.Collections.Generic;

public class Solution {
    public List<List<int>> Permute(int[] nums) {
        var result = new List<List<int>>();
        Backtrack(result, new List<int>(), nums);
        return result;
    }

    private void Backtrack(List<List<int>> result, List<int> currentPermutation, int[] nums) {
        if (currentPermutation.Count == nums.Length) {
            result.Add(new List<int>(currentPermutation));
        } else {
            for (int i = 0; i < nums.Length; i++) {
                if (currentPermutation.Contains(nums[i])) continue;
                currentPermutation.Add(nums[i]);
                Backtrack(result, currentPermutation, nums);
                currentPermutation.RemoveAt(currentPermutation.Count - 1);
            }
        }
    }
}