L9. Combination Sum II | Leetcode | Recursion | Java | C++

Main ideas / concepts conveyed

• The video explains how to solve LeetCode “Combination Sum II” using recursion (backtracking) in Java/C++.
• Goal of the problem:
  • Given an array of candidate numbers and a target sum, return all unique combinations where the sum equals the target.
• Key constraints emphasized:
  • Each candidate can be used at most once in a combination.
  • The result must not contain duplicate combinations.
• Core approach described:
  • Sort the candidates so duplicates can be handled cleanly.
  • Use DFS/backtracking:
    • Maintain a running current sum.
    • Track an index (start position) to control which elements can be chosen next.
    • Stop when current sum == target (record the combination).
    • Stop when current sum > target (prune).
  • Handle duplicates by skipping equal values at the same recursion depth (the typical “skip duplicates” rule).

Method / instructions (as described in the video)

Preprocessing

• Sort the candidate array.

Backtracking function (conceptual steps)

Inputs typically include:

• startIndex (or similar): the position from which choices are allowed
• currentSum
• currentCombination (list being built)

Steps:

1. If currentSum == target:
   • Add currentCombination to the answer list.
   • Return.
2. If currentSum > target:
   • Return (prune this branch).
3. For each index i from startIndex to the end of the array:
   • Choose candidates[i] (append to currentCombination).
   • Recurse with:
     • startIndex = i + 1 (ensures each element is used at most once)
     • currentSum + candidates[i]
   • After recursion:
     • Remove the last chosen element (backtrack).
   • Duplicate avoidance:
     • If i > startIndex and candidates[i] == candidates[i - 1], skip choosing candidates[i] at this depth to prevent duplicates.

Uniqueness guarantee

• Sorting combined with the depth-level skip duplicates condition ensures the output does not contain duplicate combinations.

Examples / walkthrough references

• The subtitles reference standard example-style reasoning:
  • Combinations are built by picking values in order, then moving recursion forward using i + 1.
  • Invalid cases (e.g., sum exceeding target or duplicate generation) are rejected/avoided via:
    • Pruning (currentSum > target)
    • Duplicate skipping

Complexity discussion (high level, as conveyed)

• Brute force is reduced using pruning, but the problem still has exponential behavior in the worst case.
• Pruning and duplicate skipping improve performance in practice.
• The video mentions time complexity in terms of recursion/subset exploration plus sorting/log factors, but the exact formula is hard to read from the subtitles—main message: exponential search with pruning.

Call-to-action / channel content

• The speaker repeatedly asks viewers to subscribe, like, and share, and references other videos/parts (e.g., “part one” style series).

Speakers / sources featured

• Primary speaker: The YouTube channel host (referred to as “Aayog” / “Channel Aayog” in the subtitles).
• No other clearly identifiable speakers are distinguishable from the auto-generated subtitles.