Combination Sum

Google Interview Question

Problem Overview

Difficulty: Medium
LeetCode Pattern: Backtracking

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

Note: The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Input:
· candidates = [2,3,5]
· target = 8

Output:
· [[2,2,2,2],[2,3,3],[3,5]]

Explanation:
· 2+2+2+2 = 8
· 2+3+3 = 8
· 3+5 = 8

Input:
· candidates = [2,3,6,7]
· target = 7

Output:
· [[2,2,3],[7]]

Explanation:
· 2 + 2 + 3 = 7
· 7 = 7

---

Step 1: Clarify Requirements

• Can the candidates array be empty?

  • Yes. Return empty list.

• Can input array contain negatives?

  • No. All numbers are positive.

• Does the combination order matter?

  • No. [2,2,3] is same as [3,2,2].

---

Step 2: Discuss Approaches

1/ Brute Force (Suboptimal ⚠️)

• Logic:

  • Generate all possible combinations

  • For each combination:

    • Check if sum equals target

  • Return only valid combinations

• Big O:

  • Time Complexity: O(2ⁿ)

  • Space Complexity: O(n)

  • Generates many unnecessary paths

---

2/ Use Backtracking (Optimal ✅)

• Logic:

  • Use a DFS helper function

    Maintain:

    • current path

    • remaining target

  • At each step:

    • If target == 0:

      • Add copy of path to result

    • If target < 0:

      • Stop exploring path

    • Include Case:

      • Pick current element

      • Recurse with same index

    • Exclude Case:

      • Don’t pick current element

      • Recurse with next index

• Big O:

  • Time Complexity: O(2ⁿ)

  • Space Complexity: O(n)

  • Efficient due to pruning

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if candidates contain duplicates?

  • Sort the original array.

  • Skip duplicates while backtracking.

• What if numbers cannot be reused?

  • Move to next index in both cases:

    • Include Case

    • Exclude Case

• What if we want result in sorted order?

  • Sort candidates first.

  • Build paths in order.