FastPrep
Problem · Array

Combination Sum with Single-Use Values

Learn this problem
● MediumPinterest logoPinterestFULLTIMEPHONE SCREEN

Problem statement

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

  • Each array position may be selected at most once.
  • The input may contain duplicate values, but the result must not contain duplicate combinations.
  • Each combination must be nondecreasing, and the result must be in lexicographic order.

Function

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

Examples

Example 1

candidates = [10,1,2,7,6,1,5]target = 8return = [[1,1,6],[1,2,5],[1,7],[2,6]]

The two input occurrences of 1 may both be used, but identical value combinations appear only once.

Example 2

candidates = [2,5,2,1,2]target = 5return = [[1,2,2],[5]]

Although 2 occurs three times, [1,2,2] is returned only once.

Example 3

candidates = [4,4,4]target = 8return = [[4,4]]

Any two input positions form the same value combination, so the result contains one row.

Constraints

  • 1 <= candidates.length <= 100.
  • 1 <= candidates[i] <= 50.
  • 1 <= target <= 30.

More Pinterest problems

drafts saved locally
public int[][] combinationSumSingleUse(int[] candidates, int target) {
    // Write your code here.
}
candidates[10,1,2,7,6,1,5]
target8
expected[[1,1,6],[1,2,5],[1,7],[2,6]]
checking account