Combination Sum

Using the given distinct positive numbers — each may be used any number of times — find every combination whose sum is exactly target.

Input:

• line 1: n target
• line 2: n distinct positive integers

Output:

• line 1: the number of combinations c
• next c lines: one combination each, its numbers in non-decreasing order; combinations in lexicographic order (compare number by number)

Constraints: 1 ≤ n ≤ 30, 2 ≤ value ≤ 40, 1 ≤ target ≤ 40.

Think about it: sort, then backtrack with a start index i: choosing a[k] recurses with start k again (reuse allowed) — never an earlier index, so 2 2 3 and 2 3 2 aren't both produced. Stop early once a[k] exceeds the remaining sum.