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

Recall & Review

beginner

What is a permutation of an array?

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

beginner

What is the base case in a recursive function to generate permutations?

The base case is when the current position reaches the length of the array, meaning a complete permutation is formed and can be recorded 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 rest, ensuring all unique orders are explored.

intermediate

How does backtracking help in generating permutations?

Backtracking restores the array to its original state after exploring one permutation path, allowing the algorithm to explore other possible permutations without interference.

intermediate

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

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

What does the base case in permutation recursion usually check?

A If the array is sorted

B If the array is empty

C If the first element is fixed

D If the current index equals the array length

The base case checks if the current index has reached the array length, meaning a full permutation is formed.

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

A To restore the original array for the next permutation

B To sort the array

C To remove duplicates

D To increase the array size

Swapping back restores the array to its original state so other permutations can be generated correctly.

How many permutations does an array of length 3 have?

A 6

B 9

C 3

D 12

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

Which technique is commonly used to generate all permutations?

A Dynamic programming

B Greedy algorithm

C Backtracking

D Binary search

Backtracking is used to explore all possible permutations by trying choices and undoing them.

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

A To reverse the array

B To fix one element at the current position

C To delete elements

D To sort the array

Swapping fixes one element at the current position to generate permutations of the remaining elements.

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

Think about how you try one choice, then undo it to try another.

Describe the steps to generate all permutations of [1, 2, 3] using swapping and recursion.

Imagine fixing one number at a time and exploring the rest.