Decompositions of a number in sums of primes (using backtracking)

[junior galleon]

Hello people of discord, I'm turning to your brilliant minds for assistance once again.... I've been faced with an assignment that I'm having trouble breaking into small enough parts for me to handle, and that may be because I lack the experience of solving similar, perhaps more simple backtracking problems.

What I need to do is to take any positive number (I've been working with the number 10) and determine all of it's decompositions as sums of prime numbers, for example, 10 = 5 + 5, 5 + 3 + 2, 2 + 2 + 2 + 2 + 2, ect.

So far, I'm pretty sure I need to first get a list of the prime numbers that are lower than the number, so for the case of 10: [7, 5, 3, 2]. Then, starting from the first number in that list (7), add it with every number in that list (including itself), if any of the results are above 10, stop going down that path, if the result for any of them is 10, push a list of the numbers used to obtain this result (the 'path') to a list of lists that I'll ultimately return, and lastly, if the result is less than 10, e.g 9, add every single prime to 9 and if the result happens to be 10, save the 'path' to this list where I keep all of my combinations of prime numbers... Anyways, after going down each branch of possibilities starting with 7, I'd continue the same process with 5, 3, and 2 and eventually get every possible combination of prime numbers that add up to 10.

Sorry if I didn't explain this very well... essentially I know I'm looking at some form of recursion, but another thing my assignment requires is that I implement this solution in both a recursive and iterative manner... Imagining this problem with an iterative solution makes my head spin even more, but I'll just start with the recursive implementation and will hopefully after that have gained a better understanding of the solution.

I feel like I'm close to the solution, as if it's on the tip of my tongue, but I don't know how to translate my ideas into more codeable pieces...

[dapper falcon]

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

[junior galleon]

Sorry, I was hitting the character limit, but I don't know... I can solve the problem myself on paper and it makes sense to me with my internal logic, I just don't know how to translate it into the computer's logic...

[hardy turtle]

did a first attempt and got this, didnt really aim for performance and the printing is scuffed still

you aim for something like this?

IF currentSum == myEnteredNumber THEN
    print(myList)
IF currentSum < myEnteredNumber THEN

FOR currentNumber = 2 UNTIL myEnteredNumber
    IF isPrime(currentNumber) THEN
        currentSum = currentSum + currentNumber
        myList.pushBack(currentNumber)

        myBackTrcakingFunction(myList, currentSum, myEnteredNumber)

        currentSum = currentSum - currentNumber
        myList.popBack()
    ENDIF
ENDFOR

ENDIF

you could definitely have all the primes till the entered number precomputed

[hardy turtle]

i think this would be quite your idea right, except that you would have all prime number precomputed in a vector or something. Then what you do is iterate over that structure and call your backtracking function as long as the current sum is lesser than your entered number

[junior galleon]

Thank you!

[dapper falcon]

@junior galleon Has your question been resolved? If so, run !solved :)

[dapper falcon]

This question thread is being automatically closed. If your question is not answered feel free to bump the post or re-ask. Take a look at !howto ask for tips on improving your question.