Combination Sum, Each Number Once

candidates are positive whole numbers that may repeat. Return every different combination that adds up to target, using each position at most once. Write each combination in increasing order and list them in dictionary order.

For [10, 1, 2, 7, 6, 1, 5] and target = 8: [1, 1, 6], [1, 2, 5], [1, 7], [2, 6].

Examples

Example 1

Input:

combination_sum_ii([10, 1, 2, 7, 6, 1, 5], 8)

Output:

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

Example 2

Input:

combination_sum_ii([2, 5, 2, 1, 2], 5)

Output:

[[1, 2, 2], [5]]

Constraints

• 0 <= len(candidates) <= 14
• 1 <= candidates[i] <= 30
• 1 <= target <= 60