Generate All Permutations of Array in DSA C# - Build from Scratch

Generate All Permutations of Array

📖 Scenario: You are working on a puzzle game where you need to find all possible ways to arrange a set of unique numbers. This helps the game create different challenges by mixing the numbers in every possible order.

🎯 Goal: Build a program that generates all possible permutations of a given array of integers and prints each permutation on a new line.

📋 What You'll Learn

Create an integer array with exact values [1, 2, 3]

Create a helper method called Permute that generates all permutations of the array

Use recursion and backtracking inside the Permute method

Print each permutation as a sequence of numbers separated by spaces

💡 Why This Matters

🌍 Real World

Generating permutations is useful in games, puzzles, testing scenarios, and solving problems where all possible arrangements need to be checked.

💼 Career

Understanding recursion, backtracking, and permutations is important for software developers working on algorithms, optimization problems, and combinatorial tasks.

1

Create the integer array

Create an integer array called nums with the exact values 1, 2, and 3.

DSA C#

# Create the integer array called nums with values 1, 2, 3
# Your code here

Hint

Use int[] nums = {1, 2, 3}; to create the array.

2

Create the Permute method signature

Create a method called Permute that takes three parameters: an integer array called nums, an integer called start, and an integer called end. The method should have a void return type.

DSA C#

int[] nums = {1, 2, 3};

// Create the Permute method with parameters int[] nums, int start, int end
// Your code here

Hint

Define the method with void Permute(int[] nums, int start, int end).

3

Implement the core logic of Permute method

Inside the Permute method, write code to generate all permutations of nums from index start to end using recursion and swapping. When start equals end, print the current permutation by joining the numbers with spaces. Use a for loop with variable i from start to end. Swap elements at start and i, call Permute recursively with start + 1, then swap back to backtrack.

DSA C#

int[] nums = {1, 2, 3};

void Permute(int[] nums, int start, int end)
{
    // Your code here
}

Hint

Use recursion with swapping and backtracking to generate permutations.

4

Call Permute and print all permutations

Call the Permute method with nums, 0 as start, and nums.Length - 1 as end to print all permutations.

DSA C#

int[] nums = {1, 2, 3};

void Permute(int[] nums, int start, int end)
{
    if (start == end)
    {
        Console.WriteLine(string.Join(" ", nums));
    }
    else
    {
        for (int i = start; i <= end; i++)
        {
            int temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;

            Permute(nums, start + 1, end);

            temp = nums[start];
            nums[start] = nums[i];
            nums[i] = temp;
        }
    }
}

// Call Permute method to print all permutations
// Your code here

Hint

Call Permute(nums, 0, nums.Length - 1); to start generating permutations.

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