Combination Sum II

Given an integer array \(A\) and a target integer \(T\), find all unique combinations in \(A\) where the sum of the numbers is equal to \(T\). Each number in \(A\) may only be used once in the combination.

Note: The solution set must not contain duplicate combinations. All combinations should be output in lexicographical order. Use a backtracking algorithm to generate all valid combinations.

For example, given \(A = [10, 1, 2, 7, 6, 1, 5]\) and \(T = 8\), a valid solution set is:

[ \begin{aligned} &[1, 1, 6],\ &[1, 2, 5],\ &[1, 7],\ &[2, 6] \end{aligned} ]

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 elements of the array \(A\).
3. The third line contains an integer \(T\), the target sum.

outputFormat

The output is written to standard output (stdout). For each valid combination, output a single line with the numbers separated by a space. The combinations must be printed in lexicographical order. If no valid combination exists, output a single line containing [].

## sample

7
10 1 2 7 6 1 5
8

1 1 6
1 2 5
1 7
2 6

</p>