How to Solve: Combination Sum Problems

How to Solve: Combination Sum Problems

(A Complete FAANG-Level Interview Guide)

? Introduction

"This pattern appears in 1 out of every 3 onsite interviews—master it, and you’ll solve backtracking problems with confidence, not panic."

? WHAT YOU NEED TO KNOW FIRST

Before tackling Combination Sum, ensure you understand: 1. Backtracking (DFS): Recursive exploration of all possible combinations, pruning invalid paths early. 2. Time Complexity of Recursion: How to analyze exponential-time algorithms (e.g., O(2^n) vs. O(n!)). 3. Hash Sets for Deduplication: Avoiding duplicate combinations when input has duplicates.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Mental Checklist for Every Combination Sum Problem:

1. Clarify Constraints
2. Can numbers be reused? (e.g., [2,2,3] vs. [2,3])
3. Are duplicates allowed in input? (e.g., [1,1,2])

4. Is the input sorted? (If not, sort it first for pruning.)

5. Choose the Right Technique

6. Backtracking (DFS): Default for listing all combinations.
7. DP/Memoization: If only counting combinations (not listing).

8. Two-Pointer/Hash Map: If problem reduces to subarray sums.

9. Sort the Input (If Unsorted)

10. Enables pruning (skip numbers > remaining target).

11. Define the Backtracking Function

12. Parameters: start_index, remaining_target, current_path, result.
13. Base case: remaining_target == 0 → add current_path to result.

14. Recursive case:

    • Loop from start_index to end of input.
    • Skip duplicates (if input has them).
    • Prune if num > remaining_target.
    • Recurse with updated remaining_target and current_path.

15. Handle Edge Cases

16. Empty input.
17. target = 0 (usually valid if empty combination is allowed).

18. Negative numbers (rare, but clarify with interviewer).

19. Optimize (If Needed)

20. Memoization: Cache (start_index, remaining_target) to avoid recomputation.

21. Meet-in-the-Middle: For large n, split input into two halves.

22. Test with Examples

23. Small input (e.g., [2,3], target=5).
24. Input with duplicates (e.g., [1,1,2], target=3).
25. Large input (e.g., n=20, target=100).

? WORKED EXAMPLES

Example 1 – Basic: Combination Sum (LeetCode 39)

Problem: Given candidates = [2,3,6,7], target = 7, return all unique combinations where numbers sum to target (numbers can be reused).

Step-by-Step Solution

1. Sort input: [2,3,6,7] (already sorted).
2. Backtracking function:
3. Start from index=0, remaining=7, path=[].
4. Loop through candidates:
   • 2: remaining=5, path=[2] → recurse.
   • 2 again: remaining=3, path=[2,2] → recurse.
   • 2 again: remaining=1 → prune (1 < 2).
   • 3: remaining=0 → add [2,2,3] to result.
   • 6: remaining=-1 → prune.
   • 7: remaining=0 → add [7] to result.
5. Result: [[2,2,3], [7]].

Python Code

def combinationSum(candidates, target):

    def backtrack(start, remaining, path):

        if remaining == 0:

            result.append(path.copy())

            return

        for i in range(start, len(candidates)):

            num = candidates[i]

            if num > remaining:

                continue  # Prune

            path.append(num)

            backtrack(i, remaining - num, path)  # Reuse same number

            path.pop()  # Backtrack


    result = []

    backtrack(0, target, [])

    return result

Time Complexity

• Worst Case: O(2^target) (each number can be used multiple times).
• Pruning: Reduces runtime significantly (e.g., skips 6 and 7 early).

Space Complexity

• O(target) (recursion depth).

Why This Works

• Backtracking explores all possible combinations.
• Pruning skips invalid paths early (e.g., num > remaining).
• Reusing numbers is allowed by passing i (not i+1) in recursion.

Example 2 – Medium: Combination Sum II (LeetCode 40)

Problem: Given candidates = [10,1,2,7,6,1,5], target = 8, return all unique combinations where numbers cannot be reused and input may have duplicates.

Step-by-Step Solution

1. Sort input: [1,1,2,5,6,7,10].
2. Backtracking function:
3. Skip duplicates in the same recursion level (e.g., skip second 1 if first 1 was skipped).
4. Prune if num > remaining.
5. Result: [[1,1,6], [1,2,5], [1,7], [2,6]].

Python Code

def combinationSum2(candidates, target):

    def backtrack(start, remaining, path):

        if remaining == 0:

            result.append(path.copy())

            return

        for i in range(start, len(candidates)):

            if i > start and candidates[i] == candidates[i-1]:

                continue  # Skip duplicates

            num = candidates[i]

            if num > remaining:

                break  # Prune (input is sorted)

            path.append(num)

            backtrack(i + 1, remaining - num, path)  # No reuse

            path.pop()


    candidates.sort()

    result = []

    backtrack(0, target, [])

    return result

Time Complexity

• O(2^n) (worst case, but pruning helps).

Space Complexity

• O(n) (recursion depth).

Why This Works

• Sorting enables pruning and duplicate skipping.
• i > start check avoids duplicate combinations (e.g., [1,1,6] vs. [1,1,6] again).

Example 3 – Hard/Follow-up: Combination Sum IV (LeetCode 377)

Problem: Given nums = [1,2,3], target = 4, return the number of possible combinations (order matters, e.g., [1,1,1,1] and [1,3] are different).

Step-by-Step Solution

1. Dynamic Programming:
2. dp[i] = number of ways to make i.
3. Base case: dp[0] = 1 (empty combination).
4. Transition: dp[i] += dp[i - num] for all num <= i.
5. Result: dp[4] = 7 (combinations: [1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1]).

Python Code

def combinationSum4(nums, target):

    dp = [0]  (target + 1)

    dp[0] = 1  # Base case

    for i in range(1, target + 1):

        for num in nums:

            if num <= i:

                dp[i] += dp[i - num]

    return dp[target]

Time Complexity

• O(target n) (pseudo-polynomial).

Space Complexity

• O(target).

Why This Works

• DP counts combinations efficiently (vs. backtracking, which would be O(n^target)).
• Order matters because we iterate through all nums for each i.

❌ Common Mistakes

?️ INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For Combination Sum problems, here’s your 30-second cheat sheet:

1. Sort the input—it lets you prune early and skip duplicates.
2. Backtrack with DFS—start from i, subtract num from target, and recurse.
3. Prune aggressively—if num > remaining, break the loop (input is sorted).
4. Skip duplicates—if i > start and nums[i] == nums[i-1], skip.
5. For counting combinations, switch to DP (dp[i] += dp[i - num]).

Test with small inputs first. If the interviewer asks for optimizations, think memoization or meet-in-the-middle. You’ve got this!

? Final Notes

• Practice: Solve LeetCode 39, 40, and 377 back-to-back.
• Whiteboard Tip: Draw the recursion tree for [2,3,6,7], target=7 to visualize pruning.
• Follow-Up: Be ready for "What if numbers are negative?" or "Can you do it in O(n) space?"

Now go crush that interview! ?