L11. Subset Sum II | Leetcode | Recursion

Main ideas / lesson

• Problem goal (LeetCode “Subset II”): Given an integer array nums that may contain duplicates, generate all subsets such that no duplicate subsets appear in the output.
• Core challenge: The standard “generate all subsets” recursion (pick / non-pick) creates duplicates when duplicates exist in nums.
• Optimization strategy: Use recursion that avoids generating the same subset multiple times by:
  • Sorting nums so duplicates are adjacent.
  • While iterating indices in recursion, skipping repeated values at the same recursion depth (i.e., only allow the first occurrence of a value for that depth).

Brute force approach discussed

• Generate all 2^n subsets using pick / non-pick recursion.
• Remove duplicates by:
  • Inserting each subset into a set (duplicates removed).
  • Converting the set back to a list of lists for the final answer.
• Drawback: Extra overhead due to set insertion and conversion back (time cost discussed as roughly m log m, where m = 2^n), which is not ideal for interviews.

Recursive optimization (detailed methodology)

Preprocessing

• Sort the input array nums so equal elements are consecutive.

Recursion state

Conceptually, the recursion function takes:

• index: current starting position in nums
• DS (data structure): current subset being built

At every recursive call

• Add a deep copy of DS to the answer list, since DS represents a valid subset.

Iterate to extend subsets

• Use a loop for i = index to n - 1:
  • Decide whether nums[i] can be appended to DS:
    • Always allowed when i == index (first choice at this recursion depth).
    • Otherwise, skip duplicates:
      • If nums[i] == nums[i-1], then do not pick nums[i] (because picking it would generate the same subset as picking the previous equal value at the same depth).

Pick / backtrack

• If picking nums[i] is allowed:
  • Append nums[i] to DS
  • Recurse with index = i + 1 (so each element is used at most once per subset)
  • After recursion returns, remove the last appended element from DS (backtracking)

Why this avoids duplicates

• Duplicates are only skipped within the same recursion level/depth, ensuring:
  • You still generate subsets that include a value,
  • But you don’t generate the same combination again from later identical values at the same depth.

Complexity discussion (as stated)

• Time complexity (roughly as explained):

  • Subset generation is still inherently tied to 2^n.
  • Additionally, copying DS into the answer adds overhead (described as about O(n) per subset in average reasoning), leading to an overall sense of 2^n * n.

• Space complexity:

  • Output storage dominates: up to 2^n subsets, each with average length around k (described conceptually).

• Auxiliary space:

  • Recursion stack depth up to O(n) (maximum depth mentioned as up to where n is 6 in the example discussion).

Pseudocode-level structure (conceptual)

• Initial call

  • recursion(0, empty_DS)

• Recursive function

  • Add deep copy of DS to answer
  • For i from index to n-1:
    • If i != index and nums[i] == nums[i-1]: continue (skip)
    • Append nums[i] to DS
    • recursion(i+1, DS)
    • Remove last element from DS (backtrack)

Sources / speakers mentioned

• Video narrator / presenter: Unspecified individual (“everyone welcome back…”, “I hope you guys…”). No name provided in the subtitles.
• Unacademy / sponsorship: Unspecified spokesperson for promotion (no direct person stated).
• Educators for the mentioned Unacademy batch:
  • Arjun
  • Nishchay
• Batch mentioned: “Unacademy learn CP initiative” and “batch Ascent” (no additional named authors).