1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

need help in backtrack algorithm

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

  1. AmaScatman

    AmaScatman New Member

    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. xpi0t0s

    xpi0t0s Mentor

    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. AmaScatman

    AmaScatman New Member

    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. 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;
    printf("\nEnter your number=");
    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. 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;
    printf("\nEnter your number=");
    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. 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. xpi0t0s

    xpi0t0s Mentor

    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. 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. xpi0t0s

    xpi0t0s Mentor

    Just printf one %d each time round a loop:
    Code:
    	printf("Enter a number: ");
    	char buf[32];
    	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

    Or, to use your example:
    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. Exactly....I am trying....and trying....and trying....
    Just because my sem is near, I am not being able to concentrate fully...
     
  11. xpi0t0s

    xpi0t0s Mentor

    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 [0], the second [1], the third [2], 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. xpi0t0s

    xpi0t0s Mentor

    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. 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. xpi0t0s

    xpi0t0s Mentor

    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. 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. xpi0t0s

    xpi0t0s Mentor

    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. xpi0t0s

    xpi0t0s Mentor

    In total I got 16384 sums adding up to 15, just using positive non-zero integers.
     
  18. I have counted them as well...that's what was confusing me...
     

Share This Page