All problems

Combination Sum II

Medium · backtracking

You are given a list candidates of positive integers and a positive integer target. The list may contain the same value more than once. Return every combination of numbers from candidates that adds up to target.

Each entry of the list can be used at most once, so a value that appears twice in candidates can be used up to twice.

Write each combination in ascending order. Two combinations are the same when they contain the same values the same number of times, and every distinct combination must appear exactly once in the answer, even when the input has repeated values. The combinations may be returned in any order. If no combination adds up to target, return an empty list.

Examples

Example 1

Input: candidates = [3, 1, 1, 2, 4], target = 5

Output: [[1, 1, 3], [1, 4], [2, 3]]

Both 1s are used in [1, 1, 3]. [1, 4] is listed once, even though either 1 could have been chosen.

Example 2

Input: candidates = [2, 2, 2], target = 4

Output: [[2, 2]]

There are three ways to pick two of the 2s, but they all make the same combination.

Example 3

Input: candidates = [5, 6], target = 4

Output: []

Every number is bigger than the target.

Constraints