Generate All Permutations of Array in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a permutation of an array?

A permutation is a way of arranging all the elements of the array in every possible order, without missing or repeating any element.

beginner

Which algorithm technique is commonly used to generate all permutations of an array?

Backtracking is commonly used to generate all permutations by building permutations step-by-step and undoing choices to explore all possibilities.

intermediate

In C++, which standard library function can generate the next permutation of an array?

The function std::next_permutation from the <algorithm> header generates the next lexicographically greater permutation of the array.

intermediate

What is the time complexity of generating all permutations of an array of size n?

The time complexity is O(n! * n) because there are n! permutations and each permutation takes O(n) time to process or print.

intermediate

Why do we swap elements during backtracking to generate permutations?

Swapping elements helps to fix one element at a position and recursively generate permutations for the remaining elements, then swap back to restore the original array for the next choice.

What does the backtracking method do when generating permutations?

A It sorts the array and stops.

B It only swaps the first two elements.

C It tries all possible element positions by swapping and then backtracks to try other options.

D It removes duplicates from the array.

Backtracking tries all possible positions by swapping elements and then reverses the swap to explore other permutations.

Which C++ function can be used to generate permutations in lexicographic order?

A std::unique

B std::sort

C std::reverse

D std::next_permutation

std::next_permutation generates the next lexicographically greater permutation of the array.

How many permutations does an array of size 3 have?

A 6

B 9

C 3

D 12

An array of size 3 has 3! = 6 permutations.

What is the main purpose of swapping elements in the permutation algorithm?

A To fix an element at a position and generate permutations of the rest

B To reverse the array

C To remove duplicates

D To sort the array

Swapping fixes one element at a position and recursively generates permutations for the remaining elements.

What is the output of generating all permutations of [1, 2]?

A [2, 1] only

B [1, 2] and [2, 1]

C [1, 2] only

D Empty array

All permutations of [1, 2] are [1, 2] and [2, 1].

Explain how backtracking generates all permutations of an array step-by-step.

Think about fixing one element and exploring the rest.

Describe the role of std::next_permutation in generating permutations and how it works.

It helps generate permutations in order without recursion.

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