Generate All Permutations of Array in DSA C# - Time & Space Complexity

Time Complexity: Generate All Permutations of Array

O(n!)

Understanding Time Complexity

We want to understand how the time needed to generate all permutations grows as the array size increases.

How does the number of steps change when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void Permute(int[] arr, int start, List<List<int>> result) {
    if (start == arr.Length) {
        result.Add(new List<int>(arr));
        return;
    }
    for (int i = start; i < arr.Length; i++) {
        Swap(arr, start, i);
        Permute(arr, start + 1, result);
        Swap(arr, start, i);
    }
}

void Swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
    

This code generates all possible orderings (permutations) of the array elements by swapping and recursively exploring each choice.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls combined with a loop that swaps elements.
• How many times: The recursion explores every possible ordering, which is factorial in the size of the array (n!).

How Execution Grows With Input

Each time we add one more element, the number of permutations multiplies by that new size.

Input Size (n)	Approx. Operations
3	6 (3 x 2 x 1)
5	120 (5 x 4 x 3 x 2 x 1)
7	5,040 (7 x 6 x 5 x 4 x 3 x 2 x 1)

Pattern observation: The number of operations grows very fast, multiplying by the next number each time the input size increases by one.

Final Time Complexity

Time Complexity: O(n!)

This means the time needed grows very fast as the array gets bigger, because we must explore every possible order.

Common Mistake

[X] Wrong: "The time grows like n squared because of the nested loops."

[OK] Correct: The loops are inside recursive calls that multiply the work factorially, not just squared. So the growth is much faster than n squared.

Interview Connect

Understanding this factorial growth helps you explain why generating all permutations is expensive and when it is practical to use in real problems.

Self-Check

"What if we only wanted permutations of length k from n elements? How would the time complexity change?"

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