Generate All Permutations of Array in DSA C# - Execution Trace

Concept Flow - Generate All Permutations of Array

Start with empty permutation

↓

Choose element not in current permutation

↓

Add element to current permutation

↓

Is permutation complete?

No→Repeat choosing next element

Yes↓

Output current permutation

↓

Backtrack: Remove last element

↩Back to choosing element

Build permutations by adding unused elements one by one, output when full, then backtrack to try other options.

Execution Sample

DSA C#

void Permute(int[] arr, List<int> current, bool[] used) {
  if (current.Count == arr.Length) {
    Print(current);
    return;
  }
  for (int i = 0; i < arr.Length; i++) {
    if (!used[i]) {
      used[i] = true;
      current.Add(arr[i]);
      Permute(arr, current, used);
      current.RemoveAt(current.Count - 1);
      used[i] = false;
    }
  }
}

Recursively build permutations by choosing unused elements, print when full, then backtrack.

Execution Table

Step	Operation	Current Permutation	Used Array	Action	Visual State
1	Start	[]	[false, false, false]	Begin recursion	[]
2	Choose arr[0]=1	[1]	[true, false, false]	Add 1	[1]
3	Choose arr[1]=2	[1, 2]	[true, true, false]	Add 2	[1 -> 2]
4	Choose arr[2]=3	[1, 2, 3]	[true, true, true]	Add 3 - permutation complete	[1 -> 2 -> 3]
5	Backtrack	[1, 2]	[true, true, false]	Remove 3	[1 -> 2]
6	Backtrack	[1]	[true, false, false]	Remove 2	[1]
7	Choose arr[2]=3	[1, 3]	[true, false, true]	Add 3	[1 -> 3]
8	Choose arr[1]=2	[1, 3, 2]	[true, true, true]	Add 2 - permutation complete	[1 -> 3 -> 2]
9	Backtrack	[1, 3]	[true, false, true]	Remove 2	[1 -> 3]
10	Backtrack	[1]	[true, false, false]	Remove 3	[1]
11	Backtrack	[]	[false, false, false]	Remove 1	[]
12	Choose arr[1]=2	[2]	[false, true, false]	Add 2	[2]
13	Choose arr[0]=1	[2, 1]	[true, true, false]	Add 1	[2 -> 1]
14	Choose arr[2]=3	[2, 1, 3]	[true, true, true]	Add 3 - permutation complete	[2 -> 1 -> 3]
15	Backtrack	[2, 1]	[true, true, false]	Remove 3	[2 -> 1]
16	Backtrack	[2]	[false, true, false]	Remove 1	[2]
17	Choose arr[2]=3	[2, 3]	[false, true, true]	Add 3	[2 -> 3]
18	Choose arr[0]=1	[2, 3, 1]	[true, true, true]	Add 1 - permutation complete	[2 -> 3 -> 1]
19	Backtrack	[2, 3]	[false, true, true]	Remove 1	[2 -> 3]
20	Backtrack	[2]	[false, true, false]	Remove 3	[2]
21	Backtrack	[]	[false, false, false]	Remove 2	[]
22	Choose arr[2]=3	[3]	[false, false, true]	Add 3	[3]
23	Choose arr[0]=1	[3, 1]	[true, false, true]	Add 1	[3 -> 1]
24	Choose arr[1]=2	[3, 1, 2]	[true, true, true]	Add 2 - permutation complete	[3 -> 1 -> 2]
25	Backtrack	[3, 1]	[true, false, true]	Remove 2	[3 -> 1]
26	Backtrack	[3]	[false, false, true]	Remove 1	[3]
27	Choose arr[1]=2	[3, 2]	[false, true, true]	Add 2	[3 -> 2]
28	Choose arr[0]=1	[3, 2, 1]	[true, true, true]	Add 1 - permutation complete	[3 -> 2 -> 1]
29	Backtrack	[3, 2]	[false, true, true]	Remove 1	[3 -> 2]
30	Backtrack	[3]	[false, false, true]	Remove 2	[3]
31	Backtrack	[]	[false, false, false]	Remove 3	[]
32	End	[]	[false, false, false]	All permutations generated	[]

💡 All elements tried at all positions, recursion ends

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	Final
current permutation	[]	[1]	[1, 2]	[1, 2, 3]	[1, 3]	[1, 3, 2]	[]	[]
used array	[false, false, false]	[true, false, false]	[true, true, false]	[true, true, true]	[true, false, true]	[true, true, true]	[false, false, false]	[false, false, false]

Key Moments - 3 Insights

Why do we mark elements as used and then unmark them?

We mark elements as used to avoid repeating them in the current permutation (see steps 2-4). After exploring that path, we unmark them to allow their use in other permutations (see backtrack steps 5-6).

Why do we output the permutation only when its length equals the array length?

Because a complete permutation must include all elements exactly once. This is shown at step 4 where the permutation length matches the array length, so we print it.

What happens if we don't remove the last element during backtracking?

If we don't remove the last element (see step 5), the next permutations will be incorrect because the current permutation will have extra elements, breaking the logic.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the current permutation?

A [1, 2]

B [1, 2, 3]

C [1, 3]

D []

💡 Hint

Check the 'Current Permutation' column at step 4 in the execution table.

At which step does the algorithm backtrack after completing the permutation [1, 3, 2]?

A Step 8

B Step 10

C Step 9

D Step 11

💡 Hint

Look for the step after the permutation is complete at step 8 in the execution table.

If the array had only two elements, how many permutations would be generated?

A 2

B 1

C 3

D 4

💡 Hint

Number of permutations for n elements is n!; check variable_tracker for 3 elements and adjust.

Concept Snapshot

Generate All Permutations of Array:
- Use recursion with backtracking
- Track used elements with a boolean array
- Add unused elements to current permutation
- When permutation length == array length, output it
- Remove last element to backtrack and try others

Full Transcript

This concept shows how to generate all permutations of an array using recursion and backtracking. We start with an empty list and add elements one by one if they are not used yet. When the current permutation has all elements, we print it. Then we remove the last element to try other possibilities. We keep track of which elements are used with a boolean array. The execution table shows each step, the current permutation, which elements are used, and the visual state of the list. Key moments explain why marking elements as used is important, why we print only full permutations, and why backtracking requires removing the last element. The visual quiz tests understanding of the permutation states and backtracking steps. This method ensures all possible orderings are generated without repeats.

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