FastPrepCombination Sum II With Negative Values
Problem · Backtracking

Combination Sum II With Negative Values

Learn this problem
● MediumByteDance logoByteDanceFULLTIMEPHONE SCREEN

Problem statement

Given an integer array candidates and an integer target, return all distinct combinations whose values sum to target. Candidates may be negative, zero, or positive.

  • Each input position may be selected at most once. Equal values from different positions may both be used.
  • Selections with the same multiset of values are one combination and must appear only once.
  • Write each combination in nondecreasing order. Return rows in lexicographic order: compare the first unequal value; if one row is a prefix of another, put the shorter row first.
  • Include the empty combination exactly when target == 0. Other zero-sum combinations must still be returned.

Return an empty outer array when no combination exists. Candidates cannot be reused indefinitely: this is a finite single-use exercise even when negative values occur.

Function

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

Examples

Example 1

candidates = [-1,0,1,1]target = 0return = [[],[-1,0,1],[-1,1],[0]]

The empty selection, [-1,0,1], [-1,1], and [0] sum to zero. The two occurrences of 1 do not create duplicate result rows.

Example 2

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

Only -3 + 4 = 1 works. A negative value cannot be reused, and each selected input position is used once.

Constraints

  • 0 <= candidates.length <= 16
  • -100 <= candidates[i] <= 100
  • -1600 <= target <= 1600
  • The input guarantees at most 500 distinct returned combinations.

More ByteDance problems

drafts saved locally
public int[][] combinationSumSigned(int[] candidates, int target) {
    // Write your code here
}
candidates[-1,0,1,1]
target0
expected[[],[-1,0,1],[-1,1],[0]]
checking account