Search code examples
mathematical-optimization

Verify if a number X can be generated based on a combination of a series (a,b,c)

I'm going crazy trying to figure out a way to make a program that does not try every single combination. A simple example: I want to know if 11 can be generated by adding up numbers from the series (2,5,10,20), is there an easy way to do this without trying every single possibility? In this case we can do it with three 2s and one 5. Thanks

Solution

  • I think I worked up some kind of a solution

    1. You must order your list, from higher to lower. It gives us [20, 10, 5, 2]
    2. Then, we're gonna work with some kind of a stack.

    we begin with n=0

    a. you put the n'th element of your list at the top of the stack.

    b. If the sum of numbers into your stack is greater than the targeted number, you remove the last element of your stack and return to point a. with n=n+1. if the element you remove from the stack is your lower number, then you also remove the element below, and return to point a. with n=(index of last removed number in your set)+1

    c. if it is not, you try to add it one more time, and return to point b.

    d. this algorithm is recursive, it stops when you remove the last number from your stack, and this number is your lower number (then you can't generate the number from your set), or when the sum of numbers in your stack is equal to your target number (then you can generate it from your set)

    run example : target 11, set [20,10,5,2]

    • stack status : empty, n=0
    • put 20 into stack : stack status : [20] > 11, removing 20 from stack => n=1
    • put 10 into stack : stack status : [10] < 11, n=1
    • put 10 into stack : stack status : [10, 10] > 11, removing 10 from stack => n=2
    • put 5 into stack : stack status : [10,5] > 11, removing 5 from stack => n=3
    • put 2 into stack : stack status : [10,2] > 11, removing 2 and 10 from stack => n=2
    • put 5 into stack : stack status : [5] < 11, n=2
    • put 5 into stack : stack status : [5,5] < 11, n=2
    • put 5 into stack : stack status : [5,5,5] > 11, removing 5 from stack => n=3
    • put 2 into stack : stack status : [5,5,2] > 11, removing 2 and 5 from stack => n=3
    • put 2 into stack : stack status : [5,2] < 11, n=3
    • put 2 into stack : stack status : [5,2,2] < 11, n=3
    • put 2 into stack : stack status : [5,2,2,2] = 11, You Won