L10. Subset Sum I | Recursion | C++ | Java

Main ideas / lessons

• The video explains the “Subset Sum” problem:
  • Given a list of n integers, compute the sum of every subset (including the null/empty subset, which contributes sum 0).
  • Return/print all subset sums in increasing order.
• It emphasizes that the number of subset sums is (2^n), because each element has a binary choice: include or exclude.
• It corrects the stated expected space complexity claim from the problem statement:
  • Since you must output/store all (2^n) sums, the space needed is effectively (O(2^n)), not (O(n)) (the speaker argues the prompt’s space complexity cannot be achieved).

Key concepts and reasoning

• Example with (n = 3) (values 3, 1, 2):

  • Total subsets including the empty subset = (2^3 = 8)
  • Subset sums (sorted) are: 0, 1, 2, 3, 4, 5, 6
    • The multiset can contain repeated sums (different subsets can yield the same sum); the speaker lists sums as they appear while enumerating choices.

• Interview strategy

  • Start with brute force: generate all subsets (the Power Set idea).
  • Then optimize using recursion (include/exclude per element), which still has exponential time but avoids extra overhead mentioned in the brute-force approach.

Methodology / instructions (detailed)

Brute force approach (as an initial interview answer)

• Generate all subsets using the power set concept.
• For each subset, compute its sum.
• Collect sums and sort them to output in increasing order.

Cost mentioned for power set generation

• Time: (2^n \cdot n)
• Space: implied to grow exponentially due to storing subsets/sums.

Recursive “optimal” approach described

The recursion is based on deciding for each index whether to pick or not pick the element.

State variables

• index (initially 0)
• sum (initially 0)
• answer: a list/data structure to store subset sums

Transition (for each index)

• If you pick arr[index]:
  • recurse with index + 1
  • update sum to sum + arr[index]
• If you do not pick arr[index]:
  • recurse with index + 1
  • keep sum unchanged

Base case

• When index == n (past the last element):
  • you’ve formed one complete subset
  • store the current sum into answer
  • return

After recursion

• Sort answer to ensure subset sums are in increasing order
• Return/print the sorted list

Recursive tree intuition (speaker’s walkthrough)

• Start at index 0 with sum = 0.
• At each index:
  • left branch = pick the element
  • right branch = not pick the element
• Leaves (when index passes the array end) correspond to complete subsets, and each leaf’s accumulated sum is recorded.

Complexity claims (as stated)

• Time complexity (recursive generation)

  • Each index has 2 choices (pick / not pick) → (2^n)
  • Plus sorting overhead for (2^n) sums, treated as an extra log factor
  • Overall stated as: exponential + sorting overhead (narration was slightly informal), with intent roughly:
    • (O(2^n \cdot n \log 2)) (as presented)

• Space complexity

  • (O(2^n)) because you must store all subset sums (and (2^n) outputs are required).

Code implementation overview (Java and C++)

Java

• Create a dynamic list/array subsets to store subset sums.
• Call the recursive function with:
  • index = 0
  • sum = 0
  • pass arr, n, and subsets
• Base case (index == n):
  • add sum to subsets
• After recursion:
  • sort subsets
  • return it

C++

• Similar structure:
  • input array arr and size n
  • vector/list subsets
  • recursive helper with (index, sum)
• Base case stores sum
• Sort the results before returning

Speakers / sources featured

• Speaker/Host (unnamed): main presenter (“hey everyone welcome back to the channel…”)
• Unacademy teachers mentioned (sponsorship)
  • Deeper God (ICPC World Finalist, 2020)
  • Arjun Arul (World Finalist, 2012 & 2013; coach at IOI/TC referenced)
  • Sanket
  • Annabeth (software/teaching background mentioned)
• Platform / sponsor
  • Unacademy