Generate All Permutations of Array in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Permutations for a 3-Element Array

What is the output of the following C# code that generates all permutations of the array [1, 2, 3]?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {1, 2, 3};
        var result = new List<List<int>>();
        Permute(arr, 0, result);
        foreach(var perm in result) {
            Console.WriteLine(string.Join(",", perm));
        }
    }

    static 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);
        }
    }

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

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

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

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

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

💡 Hint

Trace the recursive calls and swaps carefully to see the order of permutations generated.

The code uses backtracking with swapping to generate permutations. The order is lexicographic based on the swapping sequence, producing permutations in the order: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

🧠 Conceptual

intermediate

Number of Permutations for an Array of Length N

If you have an array of length N, how many unique permutations does it have?

A N!

B 2^N

C N^2

D N

💡 Hint

Think about how many choices you have for each position in the permutation.

The number of unique permutations of an array of length N is N factorial (N!). This is because for the first position you have N choices, for the second N-1, and so on, multiplying to N!.

🔧 Debug

advanced

Identify the Bug in Permutation Generation Code

What error will the following code produce when trying to generate permutations of [1, 2, 3]?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int[] arr = {1, 2, 3};
        var result = new List<List<int>>();
        Permute(arr, 0, result);
        foreach(var perm in result) {
            Console.WriteLine(string.Join(",", perm));
        }
    }

    static 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);
            // Missing swap back here
        }
    }

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

A The output will be incomplete permutations missing some sequences.

B The program will throw a NullReferenceException.

C The program will run correctly and print all permutations.

D The program will cause a StackOverflowException.

💡 Hint

Check if the array is restored after recursive calls.

The missing swap back after the recursive call causes the array to remain altered, so some permutations are skipped or incorrect. This leads to incomplete output, not an exception.

📝 Syntax

advanced

Identify Syntax Error in Permutation Code

Which option contains a syntax error in this C# permutation generation snippet?

DSA C#

static 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);
    }
}

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

B Swap(arr, start, i)

C result.Add(new List<int>(arr));

D if (start == arr.Length) {

💡 Hint

Look for missing semicolons or braces.

Option B is missing a semicolon at the end of the Swap call, causing a syntax error.

🚀 Application

expert

Count Permutations with a Fixed Element at First Position

Given an array of length N, how many permutations have the first element fixed as the original first element?

A N-1

B N!

C (N-1)!

D 2^(N-1)

💡 Hint

Fixing one element reduces the permutation problem to the remaining elements.

Fixing the first element means we only permute the remaining N-1 elements, so the count is (N-1)!.

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