# need help in backtrack algorithm

Discussion in 'C++' started by AmaScatman, Nov 6, 2008.

1. ### AmaScatmanNew Member

Joined:
Nov 6, 2008
Messages:
2
0
Trophy Points:
0
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 the number entered.. 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

2. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Can you post the code you've got so far (use code blocks to make it easier to read, just wrap the code with [ code ] and [ /code ] (without spaces)) and let us know where you're stuck - what line of code is it where you have the problem, and what is it doing that you didn't expect, or not doing that you did?

3. ### AmaScatmanNew Member

Joined:
Nov 6, 2008
Messages:
2
0
Trophy Points:
0
Code:
```
#include <iostream.h>
#include <conio.h>

int val=0,start=0;

void sumAlgo(int n){

if(start==n){ cout<<n; return ;}

val=0;
start++;

for(int i=0 ; i<n ; i++){
val=start+i;
if(n == val && i>start) cout<<start<<"+"<<i<<endl;
}

sumAlgo(n);
}

main(){
int numb;
cout<<"enter a number :";
cin>>numb;

sumAlgo(numb);
getch();
}
```
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??

4. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
For expressing it as the sum of two numbers, I found it easey...but for greater than 2, I think I need to work out further....

Code:
```#include<stdio.h>
#include<conio.h>
#include<malloc.h>

void main()
{
int *a, *b;
int i,m;
scanf("%d",&m);
a=(int *)malloc((m-1)*sizeof(int));
b=(int *)malloc((m-1)*sizeof(int));
for(i=0;i<m-1;i++)
{
a[i]=i+1;
b[i]=m-i-1;
}
for(i=0;a[i]<=b[i];i++)
{
printf("\n%d+%d=%d\n", a[i],b[i],m);
}
getch();
}
```
Cheers....

5. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
Right now I worked it out for three nos. as well....but for n nos. the printing statement is troubling me....I think it'll need more time....

Code:
```#include<stdio.h>
#include<conio.h>
#include<malloc.h>

void main()
{
int *a, *b, *c;
int i,j,k,m,sum;
scanf("%d",&m);
a=(int *)malloc((m-1)*sizeof(int));
b=(int *)malloc((m-1)*sizeof(int));
c=(int *)malloc((m-1)*sizeof(int));
for(i=0;i<m-1;i++)
{
a[i]=i+1;
b[i]=i+1;
c[i]=i+1;
}
for(i=0;i<m-1;i++)
{
for(j=0;j<m-1;j++)
{
for(k=0;k<m-1;k++)
{
sum=a[i]+b[j]+c[k];
if(sum==m)
printf("\n%d+%d+%d=%d\n", a[i],b[j],c[k],m);
else
sum=0;
}
}
}
getch();
}
```
BTW.....the program can be done in form of writing functions as well....

Cheers....

6. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
One more thing.....the last program is not void of showing repeated results, e.g. it is showing 1+1+8=10 and 1+8+1=10 and 8+1+1=10 all three....I need to work out there as well....

Cheers....

7. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Seems like a good use of recursion; top level looks at 1..n/2 (for n=10, it looks at 1-5), then deduct that from n and call itself. Subsequent levels look at 1..(n-(sum of all previous levels))/2.

8. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
Yes....that's right....

But for higher sum representation, what will be the expression??
I mean say we want to print this sum

"1+1+1+1+....n times=n" by means of printf....how are we gonna do that????
Coz, we dunno what no. of "%d"s we are gonna use....
This was the major problem I was facing...

Cheers anyway...

9. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Just printf one %d each time round a loop:
Code:
```	printf("Enter a number: ");
char buf;
fgets(buf,30,stdin);
int max=atoi(buf);
for (int i=1; i<=max; i++)
{
printf("%d ",i);
}
```
Output:
Enter a number: 7
1 2 3 4 5 6 7

Code:
```	int max=atoi(buf);
for (int i=1; i<max; i++)
{
printf("1+");
}
printf("1=%d\n",max);
```
Output:
Enter a number: 5
1+1+1+1+1=5

So you'd need to store the numbers to print in an array, then determine when in the function you need to print something (say if you're not going to recurse again for the current number, e.g. for 10 you would want to iterate further for 1+2 but not for 1+9, so if you've got {1,2} so far, you print nothing and recurse, but if you've got {1,9} then you know that adds up to 10 so you print "1+9" and don't recurse).

Ultimately what you probably want is a program that recurses only as deep as necessary, eliminates (or avoids, which is better) duplicates, and gives output something like:
Enter a number: 15
1+2+3+4+5
1+2+4+8
1+2+5+7
1+3+4+7
1+3+5+6
1+6+8
2+3+4+6
2+5+8
2+6+7
3+4+8
3+5+7
4+5+6
7+8

10. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
Exactly....I am trying....and trying....and trying....
Just because my sem is near, I am not being able to concentrate fully...

11. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Well, as I often say, how would you do it on paper?

Let's say we're finding sums of 15, and we're part way through, and we have 2 at the start of the array.
In the recursive function we want to loop, but from what to what? 1..15? Would there be any point starting at 1 if we just want increasing sums? Would there be any point starting at 2 if we want to avoid duplicates? Once we've decided where we want to start counting from, how would we work that out?

What would be the upper limit? Remember from the output above, the sums starting with 2 are 2+3+4+6, 2+5+8 and 2+6+7.

Having decided on the loop, what now goes in the loop? We want to put the current number in the loop. How do we know what entry in the array to use? The first level would use , the second , the third , is there a pattern here that we could work out from something?

After assigning something to somewhere in the array, what next? Let's say we've got 2+3. Does this add up to 15? Do we want to print anything? Do we want to recurse deeper? What about when we get to 2+13 (just realised that's missing from my output above - bug fixed). Same three questions. Would it be appropriate to use an if/else here? What would the test be? What would we do (a) if that test is true; (b) if that test is false?

Corrected output for 15:

Enter a number: 15
1+2+3+4+5
1+2+3+9
1+2+4+8
1+2+5+7
1+2+12
1+3+4+7
1+3+5+6
1+3+11
1+4+10
1+5+9
1+6+8
1+14
2+3+4+6
2+3+10
2+4+9
2+5+8
2+6+7
2+13
3+4+8
3+5+7
3+12
4+5+6
4+11
5+10
6+9
7+8

12. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Correction: the sums starting with 2 are:
2+3+4+6
2+3+10
2+4+9
2+5+8
2+6+7
2+13

13. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
But xpi0t0s, the sum beginning with 1 can also be with repeatations, I mean;
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=15
isn't it??

14. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
There aren't any repeats in the opening post. Two examples were given, neither show any repeats. The second was:

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

As you see, 1+1+1+1+1+1 wasn't listed, nor were 1+1+4, 2+2+2, 3+3 and so on.

This is why you shouldn't hijack other people's threads. If you've got *EXACTLY* the same issue then maybe it's OK but it's still better to open your own thread so that any help is specific to your situation. There's no shortage of numbers and it doesn't cost anything to create a new thread. And if you've got a different issue then it'll only create confusion, as you can see.

15. ### back from retirementNew Member

Joined:
Nov 9, 2008
Messages:
72
1
Trophy Points:
0
Occupation:
Student, UG 1st Yr., Jadavpur University
Location:
Uttarpara, West Bengal, India
Sorry....the moment I saw the thread, I went for trying it, without reading it completely....I have no intention to hijack someone's thread, not even of opening a new thread...I am extremely sorry....

16. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
Of course, if duplicates are allowed, then the sums of 15 starting with 2 are too many to list here; I count 4096. The first few:
2+1+1+1+1+1+1+1+1+1+1+1+1+1
2+1+1+1+1+1+1+1+1+1+1+1+2
2+1+1+1+1+1+1+1+1+1+1+2+1
2+1+1+1+1+1+1+1+1+1+1+3
2+1+1+1+1+1+1+1+1+1+2+1+1
2+1+1+1+1+1+1+1+1+1+2+2
2+1+1+1+1+1+1+1+1+1+3+1
2+1+1+1+1+1+1+1+1+1+4

some more:
2+1+3+2+4+1+1+1
2+1+3+2+4+1+2
2+1+3+2+4+2+1
2+1+3+2+4+3
2+1+3+2+5+1+1
2+1+3+2+5+2
2+1+3+2+6+1
2+1+3+2+7
2+1+3+3+1+1+1+1+1+1

and the last few:
2+9+4
2+10+1+1+1
2+10+1+2
2+10+2+1
2+10+3
2+11+1+1
2+11+2
2+12+1
2+13

17. ### xpi0t0sMentor

Joined:
Aug 6, 2004
Messages:
3,009
203
Trophy Points:
63
Occupation:
Senior Support Engineer
Location:
England
In total I got 16384 sums adding up to 15, just using positive non-zero integers.

Joined:
Nov 9, 2008
Messages:
72