Combination Sum IV

Medium
330.

Combination Sum IV

Combination Sum IV is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Meta interviews.

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Sequences with the same numbers in a different order count as different combinations.

Example 1

Input
nums = [1,2,3], target = 4
Output
7
Explanation
(1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1).

Example 2

Input
nums = [9], target = 3
Output
0

Example 3

Input
nums = [2,3], target = 6
Output
2
Explanation
2+2+2 and 3+3.

Constraints

  • 1 <= nums.length <= 12
  • 1 <= nums[i] <= 100
  • All elements of nums are distinct.
  • 1 <= target <= 200
  • The answer fits in a signed 32-bit integer.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var combinationSum4 = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Combination Sum IV — Solution in Python, Java & C++

Combination Sum IV solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Combination Sum IV is a medium coding problem on arrays and dynamic programming, asked in Amazon, Google, Adobe and Meta interviews.

Problem statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Sequences with the same numbers in a different order count as different combinations.

Example 1

Input: nums = [1,2,3], target = 4
Output: 7
Explanation: (1,1,1,1), (1,1,2), (1,2,1), (1,3), (2,1,1), (2,2), (3,1).

Example 2

Input: nums = [9], target = 3
Output: 0

Example 3

Input: nums = [2,3], target = 6
Output: 2
Explanation: 2+2+2 and 3+3.

Constraints

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

Hints for Combination Sum IV

  1. Hint 1

    Order matters, so the outer loop must be over the target, with the choice of number inside.

  2. Hint 2

    dp[t] = Σ dp[t - num] over every num that fits — each term is the count of sequences whose last element is num.

  3. Hint 3

    Swapping the loop order would count unordered combinations instead, which is a different problem.

How to solve Combination Sum IV

Order matters, so loop the target outside and the numbers inside: dp[t] = Σ dp[t - num] counts sequences by their last element.

Approach

  1. Set dp[0] = 1.
  2. For t from 1 to target, for each num ≤ t, dp[t] += dp[t - num].
  3. Return dp[target].

Why it works

Every ordered sequence summing to t ends in some num, and the prefix is an ordered sequence summing to t - num; the sum over num counts each sequence exactly once.

Complexity

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

Pitfalls

  • Swapping the loops counts unordered combinations — the classic Coin Change 2 mistake in reverse.

Reference solution

Python

def combinationSum4(nums, target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1
    for t in range(1, target + 1):
        for num in nums:
            if num <= t:
                dp[t] += dp[t - num]
    return dp[target]

Java

public static int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int t = 1; t <= target; t++) {
        for (int num : nums) {
            if (num <= t) dp[t] += dp[t - num];
        }
    }
    return dp[target];
}

C++

int combinationSum4(vector<int>& nums, int target) {
    vector<long long> dp(target + 1, 0);
    dp[0] = 1;
    for (int t = 1; t <= target; t++) {
        for (int num : nums) {
            if (num <= t) dp[t] += dp[t - num];
        }
    }
    return (int) dp[target];
}

JavaScript

var combinationSum4 = function(nums, target) {
    const dp = new Array(target + 1).fill(0);
    dp[0] = 1;
    for (let t = 1; t <= target; t++) {
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] <= t) dp[t] += dp[t - nums[i]];
        }
    }
    return dp[target];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming