0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want to find all such possible collections, or any one collection? The former is harder, since their number can grow rather quickly. $\endgroup$ – Gassa Jul 21 '18 at 16:13
  • $\begingroup$ Also useful would be limits or estimates on the length of the list and on the numbers themselves. $\endgroup$ – Gassa Jul 21 '18 at 16:14
  • $\begingroup$ Yes I need to find all such possible combination..Actually the main problem is big I have just given here a part Because there I have to compare between such combinations and select the best one @Gassa $\endgroup$ – Achy97 Jul 21 '18 at 16:16
  • 1
    $\begingroup$ If you want to select the best one, that doesn't mean you need all of them. You only need to find combinations that might be the best. In that case, better tell us which combination you want. See the example in my answer with gazillions of solutions $\endgroup$ – gnasher729 Jul 21 '18 at 18:13
  • $\begingroup$ You are basically looking for the solution space for a linear diophantine equation. $\endgroup$ – Sudix Jul 21 '18 at 20:20
2
$\begingroup$

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".

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.