List every combination of the candidates that adds up to the target. Each candidate may be used any number of times. A combination is written in non-decreasing order, and the same combination is listed once.
Input
The first line has k and target (1 ≤ k ≤ 10, 1 ≤ target ≤ 40). The second line has k different positive integers.
Output
The combinations in lexicographic order (compare them number by number, like words in a dictionary), one per line with the numbers separated by spaces. Print none if there are none.
Examples
4 7 2 3 6 7
2 2 3 7
3 8 2 3 5
2 2 2 2 2 3 3 3 5
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Sort the candidates, and build combinations with a path that you append to and pop from.
Hint 2
Only allow candidates from the current position onward, and pass the same position again so a number can repeat.
Hint 3
Stop the loop once a candidate is bigger than what is left (pruning).
Solution
Show one correct solution (try it yourself first)
k, target = map(int, input().split())
candidates = sorted(map(int, input().split()))
found = []
path = []
def backtrack(start, remaining):
if remaining == 0:
found.append(path[:])
return
for i in range(start, len(candidates)):
if candidates[i] > remaining:
break
path.append(candidates[i])
backtrack(i, remaining - candidates[i])
path.pop()
backtrack(0, target)
for combo in found:
print(*combo)
if not found:
print("none")