Combination Sum IV

Combination Sum IV

What is this problem about?

The Combination Sum IV coding problem is different from the others in the series. Although it has "Combination" in the title, it actually asks for the number of permutations that sum to a target. For example, if the target is 3 and the numbers are [1, 2], both (1, 2) and (2, 1) are counted as valid. You only need to return the total count, not the actual lists.

Why is this asked in interviews?

Google and Meta use the Combination Sum IV interview question to see if a candidate can distinguish between a backtracking problem (finding all sets) and a Dynamic Programming problem (counting ways). If you try to use backtracking here, you will likely hit a Time Limit Exceeded (TLE) error because the number of permutations can be astronomical.

Algorithmic pattern used

This is a Dynamic Programming problem (similar to the Coin Change or Climbing Stairs problems).

• dp[i] represents the number of permutations that sum to i.
• dp[0] = 1.
• For each amount i from 1 to target:
  • For each num in candidates:
    • If i >= num: dp[i] += dp[i - num]

Example explanation

Candidates: [1, 2, 3], Target: 4

1. dp[0] = 1
2. dp[1]: Can use 1. dp[1] = dp[0] = 1.
3. dp[2]: Can use 1 or 2. dp[2] = dp[2-1] + dp[2-2] = 1 + 1 = 2. (Ways: [1,1], [2])
4. dp[3]: Can use 1, 2, 3. dp[3] = dp[2] + dp[1] + dp[0] = 2 + 1 + 1 = 4.
5. dp[4]: dp[3] + dp[2] + dp[1] = 4 + 2 + 1 = 7. Result: 7.

Common mistakes candidates make

• Using Backtracking: Trying to generate all permutations when only the count is needed.
• Wrong Loop Order: If you put the candidates loop on the outside, you would be counting combinations instead of permutations (this would solve Combination Sum II instead).
• Integer Overflow: The number of ways can exceed 32-bit integer limits, though most interview platforms use 64-bit or specified constraints.

Interview preparation tip

Memorize this rule: "To count combinations, iterate through items first. To count permutations, iterate through the target amount first."