Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.
for example - the given set is [2,8,3] and given integer 9
Then I can tell {3,3,3} or {3,2,2,2} can be the required sets.
Unfortunately I cannot figure out the best approach (with best time complexity).. As I tried to do it using nested loops which naturally results into huge time complexity.
Any help is appreciated.
Finding all collections will generally take exponential time since there is an exponential number of solutions. For example, take { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } and sum = 1000: Take any number of tens as long as the sum stays ≤ 1000, add any number of nines as long as the sum stays ≤ 1000, add any numbers of eights, sevens, ..., twos, finally add as many ones as needed.
To find one solution I would sort the numbers in ascending order and focus on gcd's. If gcd (x, y) = 1 then every number ≥ (x-1)(y-1) can be produced using these two numbers. In your case, with gcd(2,3) = 1, every number ≥ 1*2 = 2 can be produced which already solves your problem.
To illustrate why you don't need all combinations to find the best one: Take my example, and we define the "best" combination as the one with the smallest number of numbers added. With quadrillions of combinations solving the problem, I tell you out of my head that the optimal one is "100 times the number 10".
One possible solution is based on knapsack.
Consider the list elements $a_1$, $a_2$, $\ldots$, $a_n$ in any fixed order. Calculate the following boolean function: $f (k, t)$ is true if it is possible to have the sum of exactly $t$ from some subset of $a_1$, $a_2$, $\ldots$, $a_k$, and false otherwise. Here, $k$ spans from $0$ to $n$, inclusive, and $t$ goes from $0$ to $s$: we don't need larger sums.
The calculation can be performed in $O (n \cdot s)$ using dynamic programming. Just observe that $f (k, t) = f (k - 1, t)\mathrm{~or~} f (k, t - a_k)$: for the element $a_k$ and for every possible target sum $t$, we either drop the element from consideration, or take it into our sum. In the latter case, we must have the chance to take it again, hence the transition to $(k, t - a_k)$ instead of $(k - 1, t - a_k)$.
Now, knowing which $(k, t)$ pairs are possible and which are not, we can recursively construct all possible answers in $O((n + s) \cdot R)$, where $R$ is the number of answers. Indeed, descend from $(n, s)$ down to $(0, 0)$. When we are at $(k, t)$, we can see whether $(k - 1, t)$ and $(k, t - a_k)$ are possible, and descend only into the possible branches. As every descent takes at most $n + s$ steps, finding $R$ possible answers will happen in $(n + s) \cdot R$ time. Actually, it will be faster since some descent paths share a common start, and some $a_k$ are greater than $1$.
