Unique Combination Sum

Given an array of integers and a target sum \(T\), find all unique combinations of numbers that sum up to \(T\). Each number in the array can only be used once. The solution set must not contain duplicate combinations. The numbers within each combination must be in non-decreasing order and the overall set of combinations should be printed in lexicographical order.

If there are no valid combinations, print [].

inputFormat

The input consists of three lines:

• The first line contains an integer \(n\), representing the number of elements in the array.
• The second line contains \(n\) space-separated integers.
• The third line contains the target sum \(T\).

outputFormat

Output each unique combination on a separate line. Within each line, print the numbers of the combination separated by a single space. If no valid combination exists, print [].

7
10 1 2 7 6 1 5
8

1 1 6
1 2 5
1 7
2 6