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

Recall & Review

beginner

What is a permutation of an array?

A permutation of an array is a rearrangement of its elements in any possible order. For example, for [1, 2], the permutations are [1, 2] and [2, 1].

beginner

What is the base case in a recursive function to generate all permutations of an array?

The base case occurs when the current index reaches the length of the array, meaning a complete permutation has been formed and can be processed or printed.

intermediate

Why do we swap elements during permutation generation?

Swapping elements helps to fix one element at the current position and recursively generate permutations for the remaining positions, ensuring all unique orders are explored.

intermediate

How does backtracking work in generating permutations?

Backtracking restores the array to its previous state after recursive calls by swapping elements back, allowing the algorithm to explore other permutations without side effects.

intermediate

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

The time complexity is O(n!), because there are n! (factorial of n) possible permutations to generate and process.

What does the base case in permutation generation check for?

A If the array is sorted

B If the current index equals the array length

C If the array contains duplicates

D If the first element is fixed

The base case is when the current index reaches the array length, meaning a full permutation is ready.

Why do we swap elements back after recursive calls in permutation generation?

A To restore the original array for other permutations

B To sort the array

C To remove duplicates

D To increase the array size

Swapping back restores the array so other permutations can be generated correctly.

How many permutations does an array of size 3 have?

A 3

B 9

C 6

D 12

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

Which technique is commonly used to generate all permutations?

A Backtracking

B Greedy algorithm

C Dynamic programming

D Divide and conquer

Backtracking is used to explore all possible permutations by recursive swapping and restoring.

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

A To delete elements

B To sort the array

C To reverse the array

D To fix an element at the current position

Swapping fixes one element at the current index to generate permutations of the rest.

Explain how recursion and swapping work together to generate all permutations of an array.

Think about fixing one element at a time and exploring all options for the rest.

Describe the role of backtracking in generating permutations and why it is necessary.

Consider what happens if you don't swap back after recursion.