0

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!

WildDracula
  • 1
  • Recursively you can do something like this: take one element from the array, subtract it from the number and then find if the result can be obtained by adding some of the remaining elements of the array. Stop the recursion when either the result is zero or there is one element left. – Vasili Dec 15 '21 at 19:23
  • @Vasya Thanks for answering! I've been racking my brain trying to do something similar but so far nothing worked haha The biggest problem is figuring out what to send as parameters for the recursion – WildDracula Dec 15 '21 at 22:55
  • I would pass number and array into a recursive function – Vasili Dec 16 '21 at 04:14

0 Answers0