Combination Sum II
Given an array of candidates and a target, find all unique combinations that sum to the target, each number used at most once.
Input format
The first line contains N and the target. The second line contains N positive integers (candidates, duplicates possible). Each candidate may be used at most once.
Output format
Print every unique combination summing to the target, one per line with numbers in non-decreasing order. Sort the lines lexicographically as strings. If none exists, print -1.
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
7 8
10 1 2 7 6 1 5Expected output
1 1 6
1 2 5
1 7
2 6Example 2
Input
5 8
2 5 2 1 2Expected output
1 2 5