Unique Combination Sum

Given an array of integers and a target integer T, find all unique combinations of numbers that sum up to T. Each number in the array may only be used once in each combination. Two combinations are considered unique if the frequency of at least one chosen number differs.

Formally, you are to find all combinations such that $$\sum_{i=1}^{k}a_i = T$$, where each combination is sorted in non-decreasing order.

Print each combination in a separate line with the numbers separated by a single space. The combinations should be printed in lexicographically increasing order. If no valid combination exists, output [].

inputFormat

The input is read from standard input (stdin) and consists of three lines:

1. The first line contains an integer n, the number of elements in the array.
2. The second line contains n space-separated integers representing the array elements.
3. The third line contains an integer T, the target sum.

outputFormat

For each valid combination, output a line with the combination's numbers in ascending order separated by a single space. The combinations must be printed in lexicographical order. If no valid combination exists, output [] (without quotes).

7
10 1 2 7 6 1 5
8

1 1 6
1 2 5
1 7
2 6