L6. Recursion on Subsequences | Printing Subsequences

Main ideas & lessons

• Goal of the video: Teach how to print all subsequences of an array using recursion.
• Key definition (subsequence vs subarray):
  • A subsequence is any selection of elements that maintains the original order of the array.
  • Elements in a subsequence can be contiguous or non-contiguous.
  • A subarray is always contiguous, and it can be seen as a special case of subsequence.
• Example array: [3, 1, 2] (size n = 3)
  • Single elements like 3, 1, 2 are subsequences.
  • Multi-element subsequences include: 3 1, 3 2, 1 2, 3 1 2.
  • The empty subsequence is also included (select nothing).
  • Total number of subsequences for n = 3 is 2^3 = 8.

Core recursion concept: “take” vs “not take”

For each index, there are two choices:

• Take the current element into the running subsequence.
• Not take the current element (skip it).

By making these decisions independently for every index, you generate all subsequences.

Take/Not-take mapping (pattern intuition)

Subsequence generation follows a binary-choice pattern:

• Example subsequence 3, 2 corresponds to:
  • take index of 3
  • not take index of 1
  • take index of 2

Recursive methodology (step-by-step)

Inputs to the recursion

• index: current position in the array
• ds: a dynamic list/vector holding the subsequence built so far

Base case

• If index >= n:
  • Print ds (including the empty ds, which represents the empty subsequence)
  • Return

Recursive step (two branches)

For the current index, create two branches:

1. Branch 1: Take current element

   • Add arr[index] to ds
   • Recurse with index + 1 using the updated ds
   • After returning, remove the last added element from ds (backtracking / “pop back”)

2. Branch 2: Not take current element

   • Do not modify ds
   • Recurse with index + 1

Backtracking necessity

After exploring the “take” branch, you must undo that choice before exploring “not take” at the same recursion level; otherwise, subsequences would incorrectly accumulate extra elements.

Recursion tree explanation (conceptual)

• The recursion forms a tree where:
  • Each level corresponds to an array index.
  • Each node splits into take and not take.
• When index == n, the built ds is printed.
• Example output includes:
  • 3 1 2
  • 3 1
  • 3 2
  • 3
  • 1 2
  • 1
  • 2
  • empty subsequence

Complexity analysis

• Time complexity: O(2^n * n)
  • There are 2^n subsequences.
  • Printing each subsequence can cost up to O(n) overall.
• Space complexity (auxiliary stack): O(n)
  • Recursion depth is at most n.

Speakers / sources featured

• Speaker: Video host/instructor (name not provided in subtitles; e.g., “hey everyone welcome back…”)
• Sources: None external cited. (Only the general “power set” idea is referenced.)