Combination Sum

Given a sorted array of positive integers and a target \(T\) (\(T \in \mathbb{N}\)), find all unique combinations in the array where the candidate numbers sum to \(T\). Each number may be used an unlimited number of times. The solution set must not contain duplicate combinations.

For example, if the candidate array is [2, 3, 5] and the target is 8, the valid combinations are:

• 2 2 2 2
• 2 3 3
• 3 5

inputFormat

Input is read from standard input (stdin). The first line contains the candidate numbers separated by spaces. The second line contains the target integer \(T\).

outputFormat

Output each valid combination on a separate line. In each line, print the numbers in the combination separated by a single space. The combinations should be printed in lexicographical order. If no valid combination exists, output nothing.

2 3 5
8

2 2 2 2
2 3 3
3 5