FastPrep
Problem · Array

Combination Sum with Reusable Values

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

Given an array of distinct positive integers candidates and a positive integer target, return every unique combination whose values sum to target.

  • You may select the same candidate any number of times.
  • Each combination must be nondecreasing.
  • Return the combinations in lexicographic order.

Function

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

Examples

Example 1

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

The value 2 may be reused, giving [2,2,3]. The single value 7 is the other valid combination.

Example 2

candidates = [2,3,5]target = 8return = [[2,2,2,2],[2,3,3],[3,5]]

All three nondecreasing combinations sum to 8 and are listed lexicographically.

Example 3

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

Every candidate exceeds target, so no combination is possible.

Constraints

  • 1 <= candidates.length <= 30.
  • 1 <= candidates[i] <= 40.
  • All values in candidates are distinct.
  • 1 <= target <= 40.

More Pinterest problems

drafts saved locally
public int[][] combinationSumReuse(int[] candidates, int target) {
    // Write your code here.
}
candidates[2,3,6,7]
target7
expected[[2,2,3],[7]]
checking account