Generate All Permutations of Array in DSA C++

Mental Model

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

Analogy: Imagine you have a set of different colored balls and you want to see all the ways you can line them up in a row by swapping their positions.

Array: [1, 2, 3]
Positions: 0  1  2
Start: ↑
We swap elements at and after the current position 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 itself (no change), move to index 1

[1, 2, 3] ↑ at index 1

Why: We fix the first element and permute the rest

Step 2: At index 1, swap element at 1 with itself (no change), move to index 2

[1, 2, 3] ↑ at index 2

Why: Fix second element and permute the last

Step 3: At index 2, swap element at 2 with itself (no change), record permutation [1, 2, 3]

[1, 2, 3]

Why: Reached end, save current order

Step 4: Backtrack to index 2, swap back (no change), backtrack to index 1, swap element at 1 with element at 2

[1, 3, 2] ↑ at index 2

Why: Try next swap to create new permutation

Step 5: At index 2, swap element at 2 with itself, record permutation [1, 3, 2]

[1, 3, 2]

Why: Reached end, save current order

Step 6: Backtrack to index 2, swap back, backtrack to index 1, swap back to original [1, 2, 3], backtrack to index 0, swap element at 0 with element at 1

[2, 1, 3] ↑ at index 1

Why: Change first element to next option and permute rest

Step 7: At index 1, swap element at 1 with itself, move to index 2

[2, 1, 3] ↑ at index 2

Why: Fix second element and permute last

Step 8: At index 2, swap element at 2 with itself, record permutation [2, 1, 3]

[2, 1, 3]

Why: Reached end, save current order

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

void permute(vector<int>& arr, int start, vector<vector<int>>& result) {
    if (start == arr.size()) {
        result.push_back(arr); // save current permutation
        return;
    }
    for (int i = start; i < arr.size(); i++) {
        swap(arr[start], arr[i]); // swap to fix element at start
        permute(arr, start + 1, result); // permute rest
        swap(arr[start], arr[i]); // backtrack to original
    }
}

int main() {
    vector<int> arr = {1, 2, 3};
    vector<vector<int>> result;
    permute(arr, 0, result);
    for (auto& perm : result) {
        for (int num : perm) {
            cout << num << " ";
        }
        cout << "\n";
    }
    return 0;
}

if (start == arr.size()) {

Reached end of array, record current permutation

swap(arr[start], arr[i]);

Fix element at start by swapping with element at i

permute(arr, start + 1, result);

Recursively permute remaining elements

swap(arr[start], arr[i]);

Backtrack swap to restore original order

Output

1 2 3 

1 3 2 

2 1 3 

2 3 1 

3 2 1 

3 1 2 

Complexity Analysis

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

Space: O(n! * n) to store all permutations plus O(n) recursion stack

vs Alternative: This backtracking approach is more efficient than generating all permutations by repeated insertion because it avoids redundant work and uses swaps in place.

Edge Cases

empty array

returns one permutation: the empty array

DSA C++

if (start == arr.size()) {

array with one element

returns one permutation: the array itself

DSA C++

if (start == arr.size()) {

array with duplicate elements

generates permutations including duplicates; no filtering

DSA C++

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

When to Use This Pattern

When you need to list all possible orders of a set of items, use backtracking with swapping to generate permutations efficiently.

Common Mistakes

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

Mistake: Stopping recursion too early or not reaching base case
Fix: Check if start index equals array size to record permutation

Summary

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

Use when you need every arrangement of a list, like solving puzzles or arranging items.

The key is to fix one element at a time and permute the rest, swapping back after each step.

Practice

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

easy

A. Listing all possible orders of the array elements

B. Sorting the array in ascending order

C. Finding the maximum element in the array

D. Removing duplicate elements from 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 A

4. Quick Check:

   Permutations = all orders [OK]

Hint: Permutations = all possible orders of elements [OK]

Common Mistakes:

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

2. Which of the following C++ function signatures is correct for a recursive function generating all permutations of an integer array arr with size n</> and current index start?

easy

A. void permute(int arr[], int start, int n)

B. int permute(int arr[], int n, int start)

C. void permute(int arr[], int n)

D. int permute(int arr[], int start)

Solution

1. Step 1: Check parameter order and types

   The function needs the array, current index (start), and total size (n) to generate permutations recursively.

2. Step 2: Validate return type and parameters

   It should return void (no value) and have parameters (int arr[], int start, int n) in that order.

3. Final Answer:

   void permute(int arr[], int start, int n) -> Option A

4. Quick Check:

   Correct signature = void permute(arr, start, n) [OK]

Hint: Recursive permute needs array, start index, and size [OK]

Common Mistakes:

• Wrong parameter order
• Incorrect return type
• Missing current index parameter

3. What will be the output of the following C++ code snippet?

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = start; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

int main() {
  int arr[] = {1, 2};
  permute(arr, 0, 2);
  return 0;
}

medium

A. 2 1 \n 1 2 \n

B. 1 2 \n 2 1 \n

C. 1 2 \n 1 2 \n

D. No output

Solution

1. Step 1: Trace first call with arr = {1, 2}

   Start = 0, n = 2. Swap arr[0] with arr[0] (no change), call permute with start=1.

2. Step 2: Trace second call with start=1

   Swap arr[1] with arr[1] (no change), call permute with start=2 which prints "1 2".

3. Step 3: Backtrack and swap arr[0] with arr[1]

   Array becomes {2, 1}, call permute with start=1 again.

4. Step 4: At start=1 again, swap arr[1] with arr[1], call permute with start=2 prints "2 1".

5. Final Answer:

   1 2 \n 2 1 \n -> Option B

6. Quick Check:

   All permutations of {1,2} printed [OK]

Hint: Swap and backtrack to print all orders [OK]

Common Mistakes:

• Not swapping back after recursion
• Printing before base case
• Incorrect loop range

4. Identify the error in the following code snippet for generating permutations of array arr of size n:

void permute(int arr[], int start, int n) {
  if (start == n) {
    for (int i = 0; i < n; i++) std::cout << arr[i] << ' ';
    std::cout << '\n';
    return;
  }
  for (int i = 0; i < n; i++) {
    std::swap(arr[start], arr[i]);
    permute(arr, start + 1, n);
    std::swap(arr[start], arr[i]);
  }
}

medium

A. Function should return int, not void

B. Base case condition should be start == n - 1

C. Swap should be done only once outside the loop

D. Loop should start from i = start, not 0

Solution

1. Step 1: Analyze the for loop range

   The loop swaps arr[start] with arr[i]. If i starts at 0 always, it swaps elements already fixed in previous recursion steps.

2. Step 2: Correct loop start index

   Loop should start from i = start to avoid repeating swaps and ensure correct permutations.

3. Final Answer:

   Loop should start from i = start, not 0 -> Option D

4. Quick Check:

   Loop from start to n fixes correct elements [OK]

Hint: Start loop from current index to avoid duplicate swaps [OK]

Common Mistakes:

• Starting loop from 0 causes repeated permutations
• Changing base case incorrectly
• Misplacing swap calls

5. Given an array arr = {1, 2, 2}, how many unique permutations will a correct C++ program generate if it avoids duplicates?

hard

A. 2

B. 6

C. 3

D. 4

Solution

1. Step 1: Calculate total permutations without duplicates

   For 3 elements with two 2's, total permutations = 3! / 2! = 3.

2. Step 2: List unique permutations

   They are {1,2,2}, {2,1,2}, {2,2,1} -- total 3 unique permutations.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   3! / 2! = 3 unique permutations [OK]

Hint: Divide factorial by duplicates factorial for unique count [OK]

Common Mistakes:

• Counting duplicates as unique permutations
• Using 3! = 6 without division
• Ignoring repeated elements