Unique Combination Sum II

You are given a set of candidate numbers (which might contain duplicates) and a target number \( T \). Your task is to find all unique combinations in the candidate numbers where the candidate numbers sum to \( T \). Each number in the candidate list may only be used once in the combination.

Important: The solution set must not contain duplicate combinations. The numbers in each combination should be output in non-decreasing order, and the overall list of combinations should be sorted in lexicographical order.

Input/Output Format: For this problem, the input is read from standard input (stdin) and the output should be written to standard output (stdout).

Example:

Input:
7
10 1 2 7 6 1 5
8
Output:
1 1 6
1 2 5
1 7
2 6

</p>

In the sample above, if the candidate list is [10, 1, 2, 7, 6, 1, 5] and the target is 8, then the unique combinations are:

• \( [1, 1, 6] \)
• \( [1, 2, 5] \)
• \( [1, 7] \)
• \( [2, 6] \)

inputFormat

The input consists of three lines:

1. An integer \( n \) representing the number of candidate numbers.
2. \( n \) space-separated integers representing the candidate numbers.
3. An integer representing the target sum \( T \).

You should read from standard input.

outputFormat

Output all unique combinations that sum to the target. Each combination should be printed on a separate line with the numbers separated by a single space. The combinations must be printed in lexicographical order. If no valid combination exists, output nothing.

Write to standard output.

## sample

7
10 1 2 7 6 1 5
8

1 1 6
1 2 5
1 7
2 6

</p>