dsa · medium

Combination Sum II

candidates is a list of positive integers that may contain duplicates, and target is a positive integer. Return every unique combination of values that sum to target. Each index may be used at most once (the two ones in [1,1,2] are different items).

Arguments

• candidates — positive integers; duplicates allowed; each index used at most once
• target — required combination sum

Two combinations with the same values (ignoring order) are the same and must appear once. Order of the combinations themselves does not matter.

Example

candidates = [10,1,2,7,6,1,5], target = 8 yields [[1,1,6],[1,2,5],[1,7],[2,6]]. [1,7] uses one of the ones; [1,1,6] uses both. [7,1] is the same combination as [1,7].

candidates = [2,5,2,1,2], target = 5 → [[1,2,2],[5]].

candidates = [1], target = 1 → [[1]].

Constraints

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

Examples

Example 1

Input:
[10,1,2,7,6,1,5]
8

Expected:
[[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2

Input:
[2,5,2,1,2]
5

Expected:
[[1,2,2],[5]]

Example 3

Input:
[1]
1

Expected:
[[1]]

Open in the Dojo editor