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.