Find Number of unique durations that can be created given a list of durations and an upper bound [closed]

Question

Lets say we are given a list of durations (5s, 10s, 10s, 15s, 15s, 15s, 25s, 30s....) and we want to find a list of unique durations that can be created using this list of single durations.

for example if we have the original list of (5, 5, 15, 25) we can create the following durations:

• 5 -> using one 5 element
• 10 -> using two 5 elements
• 15 -> using one 15 element
• 20 -> using one 5 element and one 15 element
• 25 -> using two 5 elements and one 15 element OR using the 25 element
• 30 -> using 25 and 5
• 35 -> using 25 and two 5s
• 40 -> using 25 and 15
• 45 -> using 25, 15 and 5
• 50 -> using all elements

As a bonus I want to limit the number of elements used as well as set an upper limit. For example I want to use a max of 2 elements, and an upper bound for the total duration of 37.

This should eliminate the options of 40, 45, and 50 because they are above the limit, and it should eliminate the option of 35, because it uses more than 2 elements.

Anyone know of a way to approach this?

Answer 1

You can recursively/dynamically calculate the answer for each prefix of the list: when adding an entry $x$ to the list, the set of sums becomes $S \mapsto S \cup \{x + a | a \in S\}$ (and you start with the singleton set $\{0\}$ when the input list is empty). Keeping $S$ as a sorted list, this can be done in $O(mn)$ time, where $m$ is the length of the input list and $n$ is the length of the output list (which a priori is $O(2^m)$).

If you want to restrict the number of summands to $M$, then keep a list of pairs (sum, number of summands), which changes the complexity to $O(mMn)$.

If you want to put an upper bound on the sums, then prune the set $S$ after each update. This will not worsen the time complexity.