Combination Sum IV

1. Define the problem

You are given an array of different positive numbers and a target. Count how many ways you can add numbers from the array together to reach the target exactly. You may use each number as many times as you want, and different orders count as different ways — so 1 + 2 and 2 + 1 are two separate answers, not one. Build the answer up from small targets. The number of ways to reach a total is the sum of the ways to reach that total minus each available number , because whatever number you use last had to be preceded by a smaller total.

Constraints

1 ≤ nums.length ≤ 200
1 ≤ nums_i ≤ 1000
All the numbers in nums are different
1 ≤ target ≤ 1000

Example

Inputnums = [1, 2, 3], target = 4

Output7

Explanation The 7 ways are 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3 and 3+1. Reordering counts separately.

2. Know the words first

In plain terms

Combination: One sequence of numbers that adds up to the target. Despite the name, order matters in this problem, so it is really a sequence.
Target: The total you are trying to reach by adding numbers together.
Building up from smaller totals: Answering the question for totals 1, 2, 3 and so on before the real target, so each new answer can reuse the ones already worked out.

3. Visualize the solution

Fill in the number of ways to reach every total up to the target

Statusinit

One way to reach 0: add nothing at all.

What happens in this step

nums = [1, 2, 3], target = 4

Total 0 holds 1 and every other total holds 0. That single 1 is the seed the rest of the row grows from.

Step 1 of 6

Steps to visualize

The row is every total from 0 to 4, with the available numbers being 1, 2 and 3.
Each cell holds how many ordered ways there are to reach that total.
Total 0 is 1: there is one way to add up to nothing, by picking nothing.
Work left to right through the totals.
For each total, try every available number as the last one added.
Add in the count already stored at total minus that number.
The last cell is the answer.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fill in the number of ways to reach every total up to the target

Statusinit

One way to reach 0: add nothing at all.

What happens in this step

nums = [1, 2, 3], target = 4

Total 0 holds 1 and every other total holds 0. That single 1 is the seed the rest of the row grows from.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function combinationSum4(nums, target) {
  const ways = new Array(target + 1).fill(0);
  ways[0] = 1;

  for (let total = 1; total <= target; total += 1) {
    for (const num of nums) {
      if (num <= total) {
        ways[total] += ways[total - num];
      }
    }
  }

  return ways[target];
}

Time: O(target * n)
Space: O(target)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3], target = 4`	`7`	example from the description
`nums = [9], target = 3`	`0`	the target cannot be reached at all
`nums = [1], target = 5`	`1`	only one number available, so only one sequence
`nums = [1, 2], target = 4`	`5`	order matters, so 1+2+1 and 2+1+1 count separately
`nums = [2, 3], target = 7`	`3`	a longer build-up with no number equal to 1
`nums = [2, 4], target = 7`	`0`	even numbers can never add up to an odd target

Combination Sum IV