I've got a problem I'm working on and I can't seem to make progress, so I thought it'd be a good idea to ask around if anyone has an input for me. I will try to explain it:
Q: Numbers can be written as a sum of other numbers. Say, 7, can be written as 6+1 or 5+2, for example. Suppose we have any positive integer. Let it be 10, for example. I give you an array of other integers, for example [1,2,3,4,5]. I want to discover how many possibilities we have to write the said number using the array of integers I gave you, without repetition.
Note: As a rule, we can not repeat numbers like this 5+5=10, we can only do things like 1+4+5 = 10. Also 1+4+5 is the same as 5+4+1.
Examples: Target number: 148 Array = [1 10 11 21 27 33 34 46 49 61 62 67 73 77 79] Answer: 19 possibilities
I hope I managed to explain the problem well. What I want to do is to find an algorithm to solve this problem recursively.
Thanks in advance everyone!