Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers cannot be reused.
Initial data. The first line contains two natural numbers N and K - desired sum and length of excluded number list. The second line lists the K distinct numbers that are excluded.
Results. Output the numbers a1 , . . . , am, whose sum is N and which satisfy the listed conditions. They can be listed in any order. If it's impossible to satisfy the conditions, output "IMPOSSIBLE".
Constraints. 1 ≤ N ≤ 1000 000 000, 0 ≤ K ≤ 1000 and all excluded number list members are between 1 and 1,000,000,000 inclusive.
This seems similar to the subset sum problem. I have implemented a tabular Dynamic Programming solution, however, that is not fast and memory-efficient enough. The time-complexity of my algorithm is O(N*(N-K)) while space-complexity is O(N).
Any ideas?
