L12. Print all Permutations of a String/Array | Recursion | Approach - 1

Main ideas / lesson conveyed

• The video explains how to solve an interview problem: print/generate all permutations of a given string or array.
• It emphasizes that:
  • Order matters in permutations.
  • The solution can be built using recursion (Approach - 1).
  • The number of permutations is factorial of n (for n elements).
• High-level reasoning about algorithm behavior:
  • Fix one element position at a time.
  • Recurse on the remaining elements.
  • Use a “visited/used” concept (or equivalent) to avoid reusing elements in the same permutation.

Method / algorithm steps (recursion-based permutation generation)

• Input assumption: you have a string/array of length n.
• Core concept: generate all possible orderings by recursively choosing the next element.
• Maintain a “used/visited” structure (e.g., boolean array):
  • used[i] = true means element at index i is already placed in the current partial permutation.
• Recursive function parameters (conceptually):
  • pos (or index): current position in the permutation being constructed.
  • current: the partial permutation being built so far.

Base case

• If pos == n:
  • output the current permutation.
  • return.

Recursive step

• For each index i from 0 to n-1:
  • if used[i] is false:
    • choose array[i] as the element at position pos
    • mark used[i] = true
    • recurse with pos + 1
    • backtrack:
      • unmark used[i] = false
      • remove/undo the chosen element from current

Complexity notes

• Time complexity: grows on the order of O(n · n!) (typical for generating and printing all permutations).
• Space complexity: O(n) for used plus recursion depth (output cost is additional).

Note: Some complexity text appears imprecise due to subtitle errors, but the factorial/permutation growth is clear.

Outcome / what the method produces

• The method outputs all permutations (in any order, depending on traversal/implementation).
• The expected count is n! permutations.

Speakers / sources featured

• No clearly identifiable speaker names due to heavily corrupted subtitles.
• Some names appear in the subtitles (e.g., Vishal Singh, Dixit, Yadav, Sunidhi, Hrithik Roshan, Govind Chaudhary, Divyanshu, Vishnu), but they are not reliably confirmed as speakers in the educational explanation.
• Primary source: an unidentified YouTube instructor/channel (the video itself), with no reliable attribution to a specific person based on the transcript.