FastPrep
Problem · Array

Count Ordered Combination Sums

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

Given an array of distinct positive integers candidates and a positive integer target, return the number of nonempty ordered sequences whose values sum to target.

  • You may reuse a candidate any number of times.
  • Two sequences with the same values in different orders count separately.

Function

countOrderedCombinationSums(candidates: int[], target: int) → int

Examples

Example 1

candidates = [1,2,3]target = 4return = 7

The sequences are [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [1,3], and [3,1].

Example 2

candidates = [2,4]target = 6return = 3

The valid ordered sequences are [2,2,2], [2,4], and [4,2].

Example 3

candidates = [5]target = 3return = 0

No sequence of reusable 5s can sum to 3.

Constraints

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

More Pinterest problems

drafts saved locally
public int countOrderedCombinationSums(int[] candidates, int target) {
    // Write your code here.
}
candidates[1,2,3]
target4
expected7
checking account