Unique Combination Sum II

You are given a collection of candidate numbers candidates (which may contain duplicates) and a target number target. Write a program to find all unique combinations in candidates where the candidate numbers sum to target. Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

The approach usually involves sorting the candidate array and then using backtracking to generate combinations. Mathematically, if we let \( S \) be the sorted list of candidate values, you are required to find all subsequences \( \{s_1, s_2, \dots, s_k\} \) such that:

[ s_1 + s_2 + \cdots + s_k = \text{target} ]

and for each candidate its frequency of usage in the combination does not exceed its frequency in candidates.

inputFormat

The input is given from standard input in the following format:

• The first line contains an integer n, the number of candidates.
• The second line contains n space-separated integers representing the candidate numbers.
• The third line contains an integer target.

For example:

7
10 1 2 7 6 1 5
8

outputFormat

Output to standard output in the following format:

• The first line should contain an integer k, the number of unique combinations found.
• Each of the next k lines contains one unique combination. In each combination, the numbers should be printed in non-decreasing order, separated by a single space.

If no valid combination exists, output a single line with 0.

## sample

7
10 1 2 7 6 1 5
8

4
1 1 6
1 2 5
1 7
2 6

</p>