Generate All Permutations of Array in DSA C#

Mental Model

We want to list every possible order of the items in the array by swapping elements step by step.

Analogy: Imagine you have 3 different colored balls and want to see all ways to line them up on a shelf by changing their order.

Array: [1, 2, 3]
Indexes:  0  1  2
Start with first index and swap with each possible index to create new orders.

Dry Run Walkthrough

Input: array: [1, 2, 3]

Goal: Generate all possible orders of the array elements.

Step 1: Start at index 0, swap element at 0 with 0 (no change)

[1, 2, 3]

Why: Begin permutations by fixing first element and permuting the rest

Step 2: Move to index 1, swap element at 1 with 1 (no change)

[1, 2, 3]

Why: Fix second element and permute the last element

Step 3: Move to index 2, reached end, record permutation [1, 2, 3]

[1, 2, 3]

Why: One full permutation is ready to save

Step 4: Backtrack to index 1, swap element at 1 with 2

[1, 3, 2]

Why: Change second element to next option to generate new permutations

Step 5: Move to index 2, reached end, record permutation [1, 3, 2]

[1, 3, 2]

Why: Another full permutation is ready to save

Step 6: Backtrack to index 0, swap element at 0 with 1

[2, 1, 3]

Why: Change first element to next option to generate new permutations

Step 7: At index 1, swap element at 1 with 1 (no change)

[2, 1, 3]

Why: Fix second element and permute the last

Step 8: At index 2, reached end, record permutation [2, 1, 3]

[2, 1, 3]

Why: Save this permutation

Step 9: Backtrack to index 1, swap element at 1 with 2

[2, 3, 1]

Why: Change second element to next option

Step 10: At index 2, reached end, record permutation [2, 3, 1]

[2, 3, 1]

Why: Save this permutation

Step 11: Backtrack to index 0, swap element at 0 with 2

[3, 2, 1]

Why: Change first element to last option

Step 12: At index 1, swap element at 1 with 1 (no change)

[3, 2, 1]

Why: Fix second element

Step 13: At index 2, reached end, record permutation [3, 2, 1]

[3, 2, 1]

Why: Save this permutation

Step 14: Backtrack to index 1, swap element at 1 with 2

[3, 1, 2]

Why: Change second element to last option

Step 15: At index 2, reached end, record permutation [3, 1, 2]

[3, 1, 2]

Why: Save this permutation

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Permutations {
    static void Generate(int[] arr, int start, List<int[]> result) {
        if (start == arr.Length) {
            // Record a copy of current permutation
            int[] perm = new int[arr.Length];
            Array.Copy(arr, perm, arr.Length);
            result.Add(perm);
            return;
        }
        for (int i = start; i < arr.Length; i++) {
            // Swap current index with i
            int temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;

            Generate(arr, start + 1, result); // Recurse for next index

            // Swap back to restore original array
            temp = arr[start];
            arr[start] = arr[i];
            arr[i] = temp;
        }
    }

    static void Main() {
        int[] input = {1, 2, 3};
        List<int[]> permutations = new List<int[]>();
        Generate(input, 0, permutations);
        foreach (var perm in permutations) {
            Console.WriteLine(string.Join(", ", perm));
        }
    }
}

if (start == arr.Length) {

Reached end of array, record current permutation

Array.Copy(arr, perm, arr.Length);

Make a copy of current array state to save as a permutation

for (int i = start; i < arr.Length; i++) {

Try swapping current start index with each index i to generate permutations

int temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;

Swap elements at start and i to change order

Generate(arr, start + 1, result);

Recurse to fix next element and generate deeper permutations

temp = arr[start]; arr[start] = arr[i]; arr[i] = temp;

Swap back to restore original order before next iteration

Output

1, 2, 3

1, 3, 2

2, 1, 3

2, 3, 1

3, 1, 2

3, 2, 1

Complexity Analysis

Time: O(n! * n) because there are n! permutations and copying each permutation takes O(n)

Space: O(n! * n) to store all permutations of length n

vs Alternative: This backtracking approach is efficient compared to generating permutations by repeated insertion which can be more complex and less intuitive

Edge Cases

empty array

Returns a list with one empty permutation

DSA C#

if (start == arr.Length) {

array with one element

Returns a list with that single element as the only permutation

DSA C#

if (start == arr.Length) {

array with duplicate elements

Generates permutations including duplicates; no filtering of duplicates

DSA C#

for (int i = start; i < arr.Length; i++) {

When to Use This Pattern

When asked to list all possible orders or arrangements of items, use backtracking with swapping to generate all permutations efficiently.

Common Mistakes

Mistake: Not swapping back after recursive call, causing incorrect array state
Fix: Always swap back to restore original order after recursion

Mistake: Adding reference to array instead of a copy, causing all results to be the same
Fix: Make a copy of the array before adding to results

Summary

Generates all possible orders of elements in an array by swapping and backtracking.

Use when you need to find every arrangement of a set of items.

The key is to swap elements to fix one position at a time and recurse for the rest.

Practice

1. What does the process of generating all permutations of an array mean?

easy

A. Removing duplicate elements from the array

B. Sorting the array in ascending order

C. Listing all possible orders of the array elements

D. Finding the largest element in the array

Solution

1. Step 1: Understand permutations

   Permutations are all possible ways to arrange elements in order.

2. Step 2: Apply to array elements

   Generating all permutations means listing every possible order of the array elements.

3. Final Answer:

   Listing all possible orders of the array elements -> Option C

4. Quick Check:

   Permutations = All orders [OK]

Hint: Permutations = all ways to reorder elements [OK]

Common Mistakes:

• Confusing permutations with sorting
• Thinking permutations remove duplicates
• Assuming permutations find max/min

2. Which of the following C# method signatures is correct for a function that generates all permutations of an integer array and returns a list of integer arrays?

easy

A. void GeneratePermutations(int[] nums)

B. List<int> GeneratePermutations(int nums)

C. int GeneratePermutations(List<int> nums)

D. List GeneratePermutations(int[] nums)

Solution

1. Step 1: Identify input and output types

   The input is an integer array, so parameter type is int[]. The output is all permutations, so a list of int arrays is suitable.

2. Step 2: Match method signature

   List GeneratePermutations(int[] nums) returns List and takes int[] as input, matching the requirement.

3. Final Answer:

   List GeneratePermutations(int[] nums) -> Option D

4. Quick Check:

   Input int[], output List of int[] [OK]

Hint: Input array, output list of arrays for permutations [OK]

Common Mistakes:

• Using void return type when output is needed
• Wrong parameter types like List<int> instead of int[]
• Returning int instead of list of arrays

3. What is the output of the following C# code snippet?

var result = GeneratePermutations(new int[] {1, 2});
foreach(var perm in result) {
    Console.WriteLine(string.Join(",", perm));
}

List GeneratePermutations(int[] nums) {
    var list = new List();
    void Backtrack(int start) {
        if (start == nums.Length) {
            list.Add((int[])nums.Clone());
            return;
        }
        for (int i = start; i < nums.Length; i++) {
            int temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
            Backtrack(start + 1);
            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
        }
    }
    Backtrack(0);
    return list;
}

medium

A. 1,2
2,1

B. 1,2
1,2

C. 2,1
1,2

D. 2,1
2,1

Solution

1. Step 1: Understand the backtracking process

   The code swaps elements starting from index 0 and generates permutations by recursive calls.

2. Step 2: Trace permutations generated

   For input [1,2], permutations are [1,2] and [2,1]. The code prints these in order.

3. Final Answer:

   1,2 2,1 -> Option A

4. Quick Check:

   Permutations of [1,2] = 1,2 and 2,1 [OK]

Hint: Trace swaps and recursive calls carefully [OK]

Common Mistakes:

• Ignoring swap back to original after recursion
• Printing duplicates due to missing cloning
• Confusing order of permutations

4. The following code attempts to generate all permutations of an array but produces incorrect results. What is the main bug?

void GeneratePermutations(int[] nums, int start, List result) {
    if (start == nums.Length) {
        result.Add(nums);
        return;
    }
    for (int i = start; i < nums.Length; i++) {
        int temp = nums[start];
        nums[start] = nums[i];
        nums[i] = temp;
        GeneratePermutations(nums, start + 1, result);
        temp = nums[start];
        nums[start] = nums[i];
        nums[i] = temp;
    }
}

medium

A. The array is added directly without cloning, causing all entries to be the same

B. The swap back after recursion is missing

C. The base case condition is incorrect

D. The loop should start from 0 instead of start

Solution

1. Step 1: Analyze how results are stored

   The code adds the original array reference to the result list without cloning.

2. Step 2: Understand effect of adding reference

   Since the array is modified later, all entries in result point to the same array, causing incorrect results.

3. Final Answer:

   The array is added directly without cloning, causing all entries to be the same -> Option A

4. Quick Check:

   Must clone array before adding to result [OK]

Hint: Always clone array before adding to results [OK]

Common Mistakes:

• Forgetting to clone array before adding
• Missing swap back causing wrong permutations
• Incorrect base case stopping too early

5. You want to generate all unique permutations of an integer array that may contain duplicates, such as [1, 1, 2]. Which approach correctly handles duplicates to avoid repeated permutations?

hard

A. Only swap elements if they are different values

B. Sort the array first, then skip swapping duplicate elements during recursion

C. Generate all permutations without any checks and then remove duplicates at the end

D. Use a HashSet to store all permutations after generating them

Solution

1. Step 1: Sort the array to group duplicates

   Sorting helps detect duplicates easily during recursion.

2. Step 2: Skip swapping duplicate elements

   During recursion, skip swapping if the element is the same as a previously swapped one at the same recursion level to avoid repeated permutations.

3. Final Answer:

   Sort the array first, then skip swapping duplicate elements during recursion -> Option B

4. Quick Check:

   Sort + skip duplicates during recursion = unique permutations [OK]

Hint: Sort array and skip duplicates while swapping [OK]

Common Mistakes:

• Generating all then removing duplicates (inefficient)
• Not sorting array before recursion
• Only swapping if values differ ignores position importance