Count Sum Combinations

SilverShow difficulty

15000ms500MBReleased Aug 3, 2026

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

Count the multisets of values that sum to exactly target. Each value may appear any number of times, and order does not matter: {2, 2, 5} and {2, 5, 2} are the same combination.

Return the count modulo 10^9 + 7.

Examples

Example 1

Input: values = [2,3,5], target = 9
Output: 3
Explanation: The combinations are {2,2,5}, {3,3,3} and {2,2,2,3}.

Example 2

Input: values = [2,3,5], target = 1
Output: 0
Explanation: Every value exceeds 1, so no combination sums to 1.

Constraints

$1 \leq$ values.length $\leq 100$
$1 \leq$ target $\leq 10^4$
$1 \leq$ values[i] $\leq 10^4$
All values are distinct.

Loading editor...

Samples 2

Custom 0

sample

values =int[]

target =integer

Expected