Combination Sum IV

Count ordered sequences of values that add to the target.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Combination Sum IV: Build ways[total] by choosing each eligible final number and adding ways[total - number].

Input and goalCount ordered sequences of values that add to the target.

Initialize the empty sequenceFor nums = [1,2,3] and target = 4, ways[0] = 1 represents choosing nothing; all positive totals start at 0.

base1001020304

indicestotal 0..4

Recognize it

Use it when order matters, values may be reused, and every sequence reaching a total has one unambiguous final value that reduces it to a smaller solved total.

Keep true

Before processing total t, ways[0..t-1] contain exact ordered-sequence counts; after trying every num <= t, ways[t] counts each sequence exactly once by its final number.

Reuse it

To count ordered constructions, partition answers by the last decision and iterate states before choices; changing loop order can change the combinatorial object being counted.

Pattern: Counting DP.

Simple idea: To build total, place each possible value last. Add the number of ordered ways to build total - value. Start with one way to build zero: choose nothing.

def combination_sum_four(nums: list[int], target: int) -> int:
   ways = [1] + [0] * target
   for total in range(1, target + 1):
      for num in nums:
         if num <= total:
            ways[total] += ways[total - num]
   return ways[target]

Cost: $O(target\times n)$ time and $O(target)$ space.