1
$\begingroup$

I'm writing an algorithm that, given a limit N, and given a list of elements of value V, find all the possible combinations so that the sum of the elements is equal to N. Note that several elements can have the same value.

A simple example to demonstrate this, if N=16, and that we have 3 elements, a, with a value of 3, b with a value of 3 and c with a value of 4, we have:

a+a+a+a+c = 12
a+b+a+b+c = 12
c+c+c+c = 12
b+b+a+b+c = 12
etc...

The algorithm I wrote is pretty straightforward, yet I have a huge trouble making it generic. Indeed, my algorithm depends on the numbers of elements given as input. Here is what I came up with, in pseudo-code:

Input: a list of element (input)
Output: A list of elements so that the sum of their value == N (output)

FOR element_1 IN input
    sum := element_1.value

    IF sum EQUALS N
        output.push([element_1])

    FOR element_2 IN input
        sum := element_2.value

        IF sum EQUALS N
            output.push([element_1, element_2])

        FOR element_3 IN input
            // etc, there will be as much inner for loops are there are elements in input

RETURN output

Note that the algorithm is working, and the results are correct.

The problem here is that my algorithm depends on how many numbers there are in the input list. To be precise, the algorithm will work if there are less elements in the input list than there are inner for loops, and fail otherwise. Thus, I wondered, is this possible to write this algorithm using recursion ? So that I can write a generic code, that will adapt to the length of the input list.

I tried, yet didn't succeed, I don't know much about algorithmic, and I wondered if there are cases where recursion cannot be applied, and if this case is one of them.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ I'm not really sure what you're asking. Any program that can be written can be written with recursion instead of loops. $\endgroup$ – David Richerby Mar 12 '17 at 14:00
  • $\begingroup$ Yes, this can be written using recursion, and it's a nice programing exercise. I suggest trying to tackle it on your own. You'll have to add additional parameters to your recursive procedure. $\endgroup$ – Yuval Filmus Mar 12 '17 at 14:43
  • 1
    $\begingroup$ @EddaSnorra We had a question about it recently, along the lines of whether all recursions could be rewritten as iteration and/or vice-versa. I can't find it right now but you probably have a little more motivation than I do. :-) $\endgroup$ – David Richerby Mar 12 '17 at 14:47
  • $\begingroup$ Look at the most well-known theorems of a man named Kleene. :) $\endgroup$ – Raphael♦ Mar 12 '17 at 15:14
1
$\begingroup$

Off the top of my head i would perform a recursion this way:

Solve(N,V,target_value):
    if target_value == 0:
        return {}
    if target_value<0 or |V|==0:
        return false
    for 0<=i<N:
        sol = Solve(N-1,V\V[i],target_value-V[i]
        if sol is feasible:
            add [V[i]+sol] to the list of feasible solutions
    if there are any feasible solutions, return them. else return false.

This is obviously pseudo-code that needs to be tweaked a bit. But the general idea is to reduce the problem instance by thinking "If I take element i, what other elements do I have to take?". So assuming you take element i, you reduce the target value and exclude i from the available other elements and perform a recursive call.

The recursion base is reached when:

  1. The target value becomes negative (= we put too many elements into the sack already!)
  2. We used up all elements and still didn't reach the target value! The problem is therefore unsolvable
  3. We reached the target value and can return the current chain of elements. This is done by returning an empty list, which is then filled when the stack is being unwinded (line 9).
|cite|improve this answer
$\endgroup$

Your Answer

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