754. Combination Sum II (Each Element Used Once)

Given an array of positive integers candidates (which MAY contain duplicates) and a positive integer target, return all unique combinations of candidates whose elements sum to exactly target. Each element may be used AT MOST ONCE in each combination. The output must be canonicalized:
1. Each combination is in non-decreasing order.
2. The list of combinations is sorted lexicographically.
3. Duplicate combinations are removed.

Input: An array of positive integers and a target, formatted as "[c1,c2,...], target".

Output: Canonically sorted list of distinct combinations.

Examples

Input: [10,1,2,7,6,1,5], 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: Four distinct combinations sorted lex.

Input: [2,5,2,1,2], 5
Output: [[1,2,2],[5]]
Explanation: Two distinct combinations; note {2,2,1} has been sorted.

Input: [1], 2
Output: []
Explanation: No way to make 2 with a single 1 used once.

Constraints

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

Asked by