Combination Sum IV

You are given an array nums of distinct positive integers and a positive integer target.

Count the sequences of numbers taken from nums that add up exactly to target. Each number may be used any number of times, and order matters: (1, 2) and (2, 1) are two different sequences. Despite the traditional name, you are counting ordered sequences, not combinations.

Return that count. The tests guarantee it fits in a 32-bit signed integer.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• All values in nums are distinct.
• 1 <= target <= 1000
• The answer fits in a 32-bit signed integer.

Pattern Path · Dynamic Programming · problem 158 of 169

Start simple

Recursively try every number as the next element until the remaining sum hits 0 or goes negative: exponential time, since the same remainders are recomputed over and over.

The key idea

Classify every valid sequence by its last element. If a sequence summing to t ends in x, removing that x leaves a sequence summing to t - x, and conversely any sequence for t - x plus a final x is a sequence for t. Different last elements give different sequences, so nothing is counted twice:

ways[t] = sum of ways[t - x] for each x in nums with x <= t, with ways[0] = 1 for the empty sequence.

Computing ways for t = 1, 2, ..., target in increasing order guarantees every value you read is already final. The answer is ways[target].

Note the loop order. Putting the target loop outside and the numbers loop inside lets any number appear in any position, which counts ordered sequences. Swapping the loops (numbers outside) would only allow numbers in the order they appear in nums, which counts unordered combinations instead, a different problem. The table has target + 1 entries and each looks at every number once, so the work is O(target · n).

Complexity

• Time: O(target · n)
• Space: O(target)

Python

class Solution:
    def combinationSum4(self, nums, target):
        # ways[t] = number of ordered sequences from nums that sum to t
        ways = [0] * (target + 1)
        ways[0] = 1                      # the empty sequence

        for t in range(1, target + 1):
            for x in nums:               # x is the last number of the sequence
                if x <= t:
                    ways[t] += ways[t - x]
        return ways[target]

JavaScript

var combinationSum4 = function(nums, target) {
  // ways[t] = number of ordered sequences from nums that sum to t
  const ways = new Array(target + 1).fill(0);
  ways[0] = 1;                        // the empty sequence

  for (let t = 1; t <= target; t++) {
    for (const x of nums) {           // x is the last number of the sequence
      if (x <= t) ways[t] += ways[t - x];
    }
  }
  return ways[target];
};

What the interviewer is checking

The interviewer checks whether you can derive a recurrence from a "last choice" argument, and whether you understand how loop order decides between counting permutations and combinations.

Mistakes to avoid

• Swapping the loops, which counts unordered combinations instead of ordered sequences.
• Starting with ways[0] = 0, which makes every count zero.
• Plain recursion without memoisation, which is exponential.
• Integer overflow in fixed-width languages on intermediate entries that are never used for the answer.

Follow-ups to expect

• What if nums could contain negative numbers? (Infinite sequences; cap the length.)
• How do you count unordered combinations? (Swap the loops.)
• How would you list the sequences? (Backtracking; output can be huge.)

In real software

Counting the ways to compose a value from building blocks where order matters appears in tiling and step-climbing problems, in counting message encodings, and in analysing how many packet sequences fill a fixed-size frame.

Practice next