eolymp
bolt
Try our new interface for solving problems
Problems

Sum it up

Sum it up

Given a specified total and a list of integers, find all sums from the list that add up to the total. For example if the specified total is \textbf{4} and the list is \textbf{4 3 2 2 1 1}, then we find \textbf{Sums of 4:43+12+22+1+1} \InputFile The input file may contain any positive number of lists. The data for each list will occupy two lines. The first of the two lines contains the specified total and the length of the list. The second line contains the list itself. All numbers will be separated by one or more blanks. The numbers in each list appear is decreasing order, but there may be repetitions. There will be at most \textbf{12} entries in each list, and each entry will be a positive integer less than \textbf{1000}. The total will be a positive integer less than \textbf{1000}. \OutputFile For each list in the input file, the output file will contain a line with "\textbf{Sums of}", the total, and a colon. Sums will be listed one to a line. If there are no such sums, the line "\textbf{NONE}" appears. The numbers in each sum should appear in decreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. Each table of sums should be sorted so the first term of a sum that differs from the corresponding term of the next sum is larger than the term in that following sum. Each table of sums should have no duplicate lines. Each line should be terminated with a newline. The only blanks are single blanks before and after the word "\textbf{ of }".
Time limit 0.1 seconds
Memory limit 64 MiB
Input example #1
4 6 4 3 2 2 1 1
5 3 2 1 1
Output example #1
Sums of 4:
4
3+1
2+2
2+1+1
Sums of 5:
NONE