#46 Permutations - Solution

Dashboard Questions Topics Companies Sheets

The Permutations problem asks you to generate every possible ordering of the elements in a given array. Since each element must appear exactly once in every ordering, the most common and effective strategy is backtracking.

The idea is to build permutations step by step. At each position, you choose an unused number, add it to the current path, and recursively continue building the permutation. Once the current path reaches the same length as the input array, you record it as a valid permutation. After exploring that branch, you backtrack by removing the last element and trying other unused choices.

A common implementation uses a visited array or performs in-place swapping to track which elements are already included. Because every permutation must be generated, the algorithm explores a factorial number of possibilities. This approach ensures all permutations are explored systematically while keeping the recursion tree manageable.

The overall time complexity grows factorially with the size of the array, which is unavoidable since the output itself contains all permutations.

Approach	Time Complexity	Space Complexity
Backtracking (Visited Array)	O(n × n!)	O(n)
Backtracking (In-place Swapping)	O(n × n!)	O(n)

Solutions (12)

Backtracking Approach

This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.

Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.

C C++Java Python C#JavaScript

1using System;
2using System.Collections.Generic;
3
4public class Permutations {
5    public IList<IList<int>> Permute(int[] nums) {
6        var result = new List<IList<int>>();
7        Backtrack(nums, new List<int>(), result);
8        return result;
9    }
10
11    private void Backtrack(int[] nums, List<int> tempList, List<IList<int>> result) {
12        if (tempList.Count == nums.Length) {
13            result.Add(new List<int>(tempList));
        } else {
            for (int i = 0; i < nums.Length; i++) {
                if (tempList.Contains(nums[i])) continue;
                tempList.Add(nums[i]);
                Backtrack(nums, tempList, result);
                tempList.RemoveAt(tempList.Count - 1);
            }
        }
    }

    public static void Main(string[] args) {
        var permutations = new Permutations();
        int[] nums = {1, 2, 3};
        var result = permutations.Permute(nums);
        foreach (var perm in result) {
            Console.WriteLine(string.Join(", ", perm));
        }
    }
}

Explanation

This C# solution follows a backtracking strategy similar to other approaches. It uses a list to collect current permutations and checks to avoid reuse of elements in the current permutation by using a list of already used numbers.

Iterative Permutation Generation

An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.

Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.

C C++Java Python C#JavaScript