-1

Basically I'm given a vector of numbers and a target number where the goal is to find the numbers in the array that add up to the number closest to n, that is less than n and I should be able to use the same number in the vector multiple times.

For example:

{4, 3}, target: 10

In this case it should return a vector containing 3, 3, 4 in any order because their sum is 10

{60, 30}, target: 135

In this case it should return a vector containing either 60, 60 or 30, 30, 30, 30 because the sum of these is the closest sum to the target possible while it is still less than the target.

How could I make this algorithm in modern c++?

I have tried modifying https://stackoverflow.com/a/15496549/13879838 solution to what I want but I got stuck at the point that it uses a recursion and I can't find a way to check whether a solution is better than the previous one found by the algorithm.

Thomas Sablik
  • 16,127
  • 7
  • 34
  • 62
xeretis
  • 65
  • 1
  • 8
  • 2
    what have you tried? where did you get stuck? Please show a [mre] – Alan Birtles Jan 21 '21 at 09:58
  • I have tried modifying this solution: https://stackoverflow.com/a/15496549/13879838 to what I want but I got stuck at the point that it uses a recursion and I can't find a way to check whether a solution is better than the previous one found by the algorithm. – xeretis Jan 21 '21 at 10:00
  • 1
    Please take some time to take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). And of course please learn how to [edit] your questions. – Some programmer dude Jan 21 '21 at 10:00
  • 1
    If you tag your question with c++ and c++11 you should either ask something about C++ or show some C++ code. Otherwise these tags make no sense here. _"How could I make this algorithm in modern c++?"_ You don't make algorithms in a programming language. Algorithms are language-agnostic. Either you don't have an algorithm and this is just an algorithm question (unrelated to C++) or you have a complete algorithm then you should describe it in the question. In either case you should provide your approaches. – Thomas Sablik Jan 21 '21 at 10:26
  • @ThomasSablik It is primarily an algorithm question, but I would like to implement this algorithm in c++. – xeretis Jan 21 '21 at 11:30
  • _"but I would like to implement this algorithm in c++"_ but that's unrelated to the question and the question can be (and probably should be) answered in pseudo code without C++ code. This is an algorithm question and algorithm usually are language-agnostic. – Thomas Sablik Jan 21 '21 at 11:36
  • Yes, that is fine if I can get a better understanding of it that way and possibly implement it in c++ afterwards. I suppose the question is not properly phrased but what I'm trying to do is get some help with making such an **algorithm**. @ThomasSablik – xeretis Jan 21 '21 at 11:42

1 Answers1

1

If all numbers in vec are guaranteed to be positive this can easily be solved using recursion.

solve(vec, target, currentSum, solution)
  if currentSum > target
    return
  if currentSum == target
    print(solution)
    return
  for value in vec
    solve(vec, target, currentSum + value, solution + value)

You start with

solve({4, 3}, 10, 0, {})

solution + value appends and currentSum + value adds.

The next step is to find an iterative approach and to add memoization

Thomas Sablik
  • 16,127
  • 7
  • 34
  • 62