L13. Print all Permutations of a String/Array | Recursion | Approach - 2

Main ideas / lesson

• This video presents a recursion-based approach to generate all permutations of an array/string using in-place swapping (i.e., no extra map / no extra data structure for tracking used elements).
• The method works by fixing one position at a time (starting from a given index) and recursively permuting the remaining suffix.
• Backtracking is used: after exploring a choice via recursion, the algorithm undoes the swap to restore the array state.

Methodology (detailed step-by-step)

Core recursion strategy (swap-based)

Assume an array a of length n. Define a recursive function that takes:

• index = the position currently being fixed
• the array a
• an output container answer (e.g., list/vector of permutations)

At recursion level where index is fixed:

• Loop variable i goes from index to n-1:
  • Swap a[index] with a[i]
    • This choice means: “put the element currently at position i into the fixed position index.”
  • Recurse with index + 1 (fix the next position)
  • After recursion returns, swap back a[index] and a[i] to undo the change (backtracking)

Base case

• If index == n (i.e., you have fixed all positions):
  • The current array a represents one complete permutation.
  • Add a copy of a to answer.
  • Return / stop recursion.

Intuition behind swapping

• Each recursion level ensures that every number can occupy the current index by swapping it into place from the remaining range.
• By exploring all choices for each position and backtracking, the algorithm produces all possible permutations.

What permutations generation looks like (conceptual example)

• For a 3-element array [1,2,3]:
  • Fix position 0 by swapping choices (0 with 0), (0 with 1), (0 with 2)
  • For each such fixed prefix, fix position 1 similarly from the remaining elements
  • For the last index, there’s only one remaining choice, and the recursion reaches the base case to record the permutation.

The video walks through the recursion tree producing permutations like:

• 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1

Complexity notes

• Time complexity:

  • Generates n! permutations
  • For each permutation, copying/adding can cost O(n)
  • Overall stated: O(n! * n)

• Space complexity:

  • Does not use a separate “used” map/array (unlike the prior approach mentioned).
  • Extra space mainly from recursion depth: O(n)
  • Output storage inherently requires O(n! * n) (permutation list size), but the recursion itself avoids extra auxiliary structures.

Implementation outline (Java / C++)

Java approach (high-level structure)

• Use:

  • List<List<Integer>> answer
  • A recursive helper called initially with index = 0

• Base case:

  • When index reaches the end, convert/store the current nums arrangement as a List<Integer> and add to answer.

• Recursive step:

  • For each i from index to n-1:
    • Swap nums[index] and nums[i]
    • Recurse with index + 1
    • Swap back (backtracking)

C++ approach (high-level structure)

• Return type: vector<vector<int>>
• Maintain:
  • vector<vector<int>> answer

• Recursive helper:

  • Parameters: index, nums, and answer

• Base case:

  • If index == n, push current nums into answer

• Recursive step:

  • For i in [index, n-1]:
    • swap nums[index] and nums[i]
    • recurse on index + 1
    • swap back

Speakers / sources featured

• No named speakers or external sources are mentioned in the provided subtitles (only an unnamed presenter/author narrating the explanation).