hi all..
i need help in solving a backtrack algorithm using c++ .

the program asks the user for a number , and the output will be all the sums of a certain number.. for example:

if the user entered 10.. the output should be:
1+2+3+4
1+2+7
1+3+6
1+4+5
1+9
2+3+5
2+8
3+7
4+6
10

example 2.. if the user entered 6.. the output should be:
1+2+3
1+5
2+4
6

These are obviously examples in recursion.

The goal of this site is not to write code for posters. Our goal is to help clarify concepts & questions so you can complete the assignment yourself. By posting code, we will be able to see what you do & do not understand so this will help focus discussion with specific questions.

When posting code, please place a [cpp] tag before any code posted & a [/cpp] tag afterwards. This will preserve formatting & color code keywords & identifiers.

I will try to give you some ideas about where to begin your program. First you might want to factorize your input and store all the factors in a set. then get all permutations of these factors that add up to the input. doesnt sound like a an efficient way to do it, but it will work. I will post something better later.

Factoring the input won't accomplish anything useful. In the description of the problem, he does not state that the sums need to be made up of factors.

A recursive solution is on the right track. Given a number n, print all the sums that add up to n - 1 plus a 1. Then print all the sums that add up to n - 2 plus a 2, etc. If you want to make sure you don't repeat sums, always pick the numbers from smallest to largest. Your algorithm will need to take a second input then, which represents the smallest number you want to include as part of the sum.

You'll need to write a function getSums(i, n) that returns all the sums that add up to n using distinct integers from i through n. The function will need a loop where another variable j goes from i to n. On each iteration, you'll find the sums that start with j. You can do that by calling getSums(j+1,n-j) and appending j onto the beginning of each one.

You'll also want to write a wrapper function that takes n as a parameter and calls getSums(1,n) to start the recursion.

Finally, recursion always requires a base case, so don't forget about that. To figure out the base case, note that each recursive call uses a smaller value of n.

I hope I'm explaining that well. I wrote a quick implementation of it in Matlab, and it works. It only uses 13 lines of code.

thats right, i was reading something about factors and suddenly saw this question and assumed something that was not given. apologies..

Perhaps you were thinking of perfect numbers (numbers that are the sum of their factors)?

Well actually I was reading about the Euclidean algorithm to determine the GCD which also mentions how it does not require factorization. was just looking through a book about cryptography with Coding Theory.

well thats my code so far..... it only displays 2 sums--- for example:
if the user eneter 10 the output will be:
1+9
2+8
3+7
4+6
10

so i need help in the "sumAlgo" function.. i think i should use a backtrack algorithm.... but i don't know how!!
any suggestions??

You'll need to make the recursive calls inside the loop, and n should not be a global variable (since every recursive call will change its value). Here's the Matlab code that does the job. It should point you in the right direction, without giving away the answer. Look closely at where the loop starts and ends.


It uses an array to store the values in the sum (the third parameter to getSumsHelper), and prints the whole array once all the values in the sum are found.

gr8!!! thx Blake...
i've finally done it!!!