Skip to main content

Permutations

LeetCode 46 | Difficulty: Medium​

Problem Description​

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

Constraints​

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

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

Example 2:

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

Example 3:

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

Approach​

This is a classic backtracking problem. The key idea is to build permutations incrementally:

  1. Choose: Pick an unvisited element to add to the current permutation
  2. Explore: Recursively build the rest of the permutation
  3. Unchoose: Remove the element and mark it as unvisited (backtrack)

The Backtracking Template:

void backtrack(state, choices):
    if state is complete:
        add state to results
        return
    
    for each choice in choices:
        if choice is valid:
            make choice
            backtrack(new_state, remaining_choices)
            undo choice  // backtrack

Complexity Analysis​

  • Time Complexity: $O(N \times N!)$ — There are $N!$ permutations, and copying each takes $O(N)$
  • Space Complexity: $O(N)$ — Recursion stack depth and the visited array (excluding output)

Solution​

public IList<IList<int>> Permutation(int[] nums)
{
    IList<IList<int>> result = new List<IList<int>>();
    bool[] visited = new bool[nums.Length];
    Backtrack(nums, visited, new List<int>(), result);
    return result;
}

void Backtrack(int[] nums, bool[] visited, List<int> current, IList<IList<int>> result)
{
    // Base case: permutation is complete
    if (current.Count == nums.Length)
    {
        result.Add(current.ToList()); // Add a copy
        return;
    }

    // Try each unvisited element
    for (int i = 0; i < nums.Length; i++)
    {
        if (visited[i]) continue; // Skip if already used
        
        // Choose
        visited[i] = true;
        current.Add(nums[i]);
        
        // Explore
        Backtrack(nums, visited, current, result);
        
        // Unchoose (backtrack)
        visited[i] = false;
        current.RemoveAt(current.Count - 1);
    }
}

Interview Tips​

  • Why use ToList()? — Lists are passed by reference; without copying, all results would point to the same (empty) list
  • Alternative: Swap-based approach — Instead of visited array, swap elements in place:
    void Backtrack(int[] nums, int start, IList<IList<int>> result) {
        if (start == nums.Length) { result.Add(nums.ToList()); return; }
        for (int i = start; i < nums.Length; i++) {
            Swap(nums, start, i);
            Backtrack(nums, start + 1, result);
            Swap(nums, start, i); // backtrack
        }
    }
  • Common Follow-ups: