Command Palette

Search for a command to run...

Hectal
Problem 30.6 · Knapsack DPMedium

Combination Sum IV

PatternKnapsack DP

What it teaches: Counting ordered sequences: amount in the outer loop.

Practise it on judges as “Combination Sum IV”.

The problem

Given distinct positive integers, return the number of ordered sequences (numbers reusable) that add up to target.

Example 1

Input: nums = [1, 2, 3], target = 4
Output: 7

Constraints

  • 1 ≤ n ≤ 200
  • 1 ≤ target ≤ 1000
  • The answer fits in an int

Pattern clues in the wording

  • → Order matters (despite the name)

These clues point to Knapsack DP: For each item, decide take or skip under a capacity; dp[c] is the best result using capacity c.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public int combinationSum4(int[] nums, int target) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
nums = [1,2,3]
target = 4
7
2
nums = [9]
target = 3
0

From slow to fast

Approaches

1. Amount-outer DP · O(target × n)
1

Amount-outer DP

Time O(target × n) Space O(target)

ways[0] = 1; for t = 1..target, for each x ≤ t: ways[t] += ways[t − x].

Approach 1
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] ways = new int[target + 1];
        ways[0] = 1;
        for (int t = 1; t <= target; t++)
            for (int x : nums) if (x <= t) ways[t] += ways[t - x];
        return ways[target];
    }
}

Verdict: Like Climbing Stairs with arbitrary step sizes.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No way (0)
  • Single number

Mistakes people make

  • Using the combinations loop order.

Interview

Follow-up questions

What if negative numbers were allowed?