Start learning free

LESSON 356 OF 539 · BACKTRACKING

Permutations in C#: Backtracking with a used Array

Practice O(n · n!) Read the full explanation

Given an array nums of distinct integers, return every permutation of nums: every way to put all of its numbers in a row, each number exactly once.

Return the permutations in the order you get by filling the positions from first to last and always trying the numbers in their order in nums: every permutation that starts with nums[0] comes first, then every one that starts with nums[1], and so on. Among the permutations with the same first number, the second number decides the same way, trying the numbers that are left in their order in nums; then the third, and so on. So nums itself always comes first, and nums reversed comes last.

 

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]]
Explanation: Two permutations start with 1, then two with 2, then two with 3.
After 1, the numbers left are 2 and 3, tried in that order, so [1,2,3] comes before [1,3,2].

Example 2:

Input: nums = [3,1,2]
Output: [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]]
Explanation: The numbers are tried in their order in nums, 3 then 1 then 2, not in ascending order.
After 1, the numbers left are 3 and 2, in that order in nums, so [1,3,2] comes before [1,2,3].

Example 3:

Input: nums = [1]
Output: [[1]]
Explanation: One number can be put in a row in only one way.

 

Constraints:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Build a permutation one position at a time in a list current, and keep an array used of true/false values, one per number, that says which numbers current already holds. For the next position, go through the numbers in order and skip the used ones; for each unused number, take it (mark it used and add it to current), fill the remaining positions with a recursive call, then give it back (remove it and mark it unused) so the next number can take its place. When current holds all n numbers, save a copy of it. Trying the numbers in their order in nums gives exactly the order above.

There are n! permutations. Copying each one takes n steps, and the calls that build them, fewer than e · n! in all, each loop over the n numbers, so the time is O(n · n!). Besides the answer, the extra space is O(n): current, used and one call per position.

STEP 1 OF 14
    Ctrl + Enter to check

    C# · BACKTRACKING

    Permutations in C#, explained

    Problem overview

    The method Permute receives an int[] called nums of distinct numbers and returns every permutation: every way to put all the numbers in a row, each exactly once. The result is a List<List<int>>.

    The order is fixed too. Fill the positions from first to last and always try the numbers in their order in nums. For {1, 2, 3} that gives [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]: two permutations start with 1, then two with 2, then two with 3. For {3, 1, 2} the numbers are tried as 3, then 1, then 2, not in ascending order, so the result is [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]].

    Approach: fill one position at a time

    With n numbers there are n choices for the first position, n - 1 for the second, and so on, which gives n! permutations. Backtracking builds them position by position.

    The search keeps two things: a list current with the permutation built so far, and a bool[] called used where used[i] says whether nums[i] is already in current. To fill the next position, it goes through the numbers from index 0 and skips the used ones. For each free number it:

    1. takes it: marks it used and adds it to current;
    2. fills the remaining positions with a recursive call;
    3. gives it back: removes it from current and marks it unused, so the next number in the loop can try the same position.

    When current holds n numbers, it is a whole permutation, and the search saves a copy. Because the loop always runs from index 0 in the order of nums, the permutations come out in exactly the order the lesson asks for.

    Take {1, 2, 3}. The first position tries 1; the second position then skips the used 1 and tries 2, then the third position takes 3, which saves [1,2,3]. Giving back 3 and 2, the second position tries 3, and the third takes 2, which saves [1,3,2]. Then the first position gives back 1 and tries 2, and so on.

    Step by step

    1. Create result, an empty List<List<int>>.
    2. Create used as new bool[nums.Length]. A new bool array starts with every element false: nothing is taken yet.
    3. Start the search with Backtrack(nums, used, new List<int>(), result): no position is filled and every number is free.
    4. Return result. Backtrack filled this same list.
    5. Write Backtrack as a public void method taking nums, used, current and result. Each call fills one more position and calls itself for the rest.
    6. Check for a full permutation: current.Count == nums.Length means every number is in it exactly once.
    7. Save a copy with result.Add(new List<int>(current)) and return. A snapshot is needed because current keeps changing.
    8. Loop over the candidates: for (int i = 0; i < nums.Length; i++), always from 0, to get the required order.
    9. Skip used numbers with if (used[i]) { continue; }. A number already in current can't appear twice.
    10. Mark it: used[i] = true, so the deeper calls won't take it.
    11. Add it to the end of current with Add.
    12. Recurse with the same four arguments. Nothing else needs passing, since used and current already say what is taken.
    13. Give the number back: current.RemoveAt(current.Count - 1).
    14. Unmark it: used[i] = false, so permutations built later can use it in another position.

    The solution in C#

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

    public void Backtrack(int[] nums, bool[] used, List<int> current, List<List<int>> result) {
        if (current.Count == nums.Length) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = 0; i < nums.Length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            current.Add(nums[i]);
            Backtrack(nums, used, current, result);
            current.RemoveAt(current.Count - 1);
            used[i] = false;
        }
    }
}

    The C# details worth knowing:

    • Arrays and lists are shared by reference. used, current and result are passed to Backtrack as references, so every call works on the same objects. That is why the undo steps are needed: nothing is copied automatically.
    • The copy. result.Add(current) would add the very same list object each time, and after the undo steps all the entries would be empty. new List<int>(current) makes an independent copy.
    • continue ends the current turn of the for loop and goes on with the next i. The i++ still runs.
    • Count and Length. A List<int> has Count, an array has Length. The solution uses both: current.Count and nums.Length.
    • Distinct numbers. The used array tracks positions in nums, not values. With repeated values, this code would produce duplicate permutations, which is why the lesson promises distinct numbers.

    Complexity

    Time: O(n · n!). There are n! permutations and copying each one takes n steps. The recursion has fewer than e · n! calls in all, and each call runs a loop over the n numbers, so the building work stays within the same O(n · n!) bound.

    Space: O(n) beyond the answer. current and used hold at most n items, and the recursion is at most n + 1 calls deep. The answer itself holds n! lists, which is not counted as extra space. For eight numbers that is already 40,320 permutations.

    Edge cases and common mistakes

    • One number. {1} gives [[1]].
    • Two numbers. {1, 2} gives [[1,2],[2,1]].
    • The order follows nums. For {3, 1, 2} the first permutation is [3,1,2], the array itself, and the last is its reverse, [2,1,3].
    • Forgetting used[i] = false. After the first permutation, every number stays marked and the search finds nothing more.
    • Forgetting the RemoveAt. current keeps numbers from earlier branches, so the saved permutations are wrong.
    • Adding current without copying. Every entry in the result ends up empty.

    Testing

    • {1, 2, 3} gives [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]].
    • {3, 1, 2} gives [[3,1,2],[3,2,1],[1,3,2],[1,2,3],[2,3,1],[2,1,3]].
    • {1} gives [[1]], and {1, 2} gives [[1,2],[2,1]].
    • Eight numbers give 40,320 permutations.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free