Backtracking C++

Question

I have the following problem:

How many different ticket numbers are there with n digits that add up to "sum"?

For example: 
How many different ticket numbers are there with 3 digits that add up to 4?
There are exactly 15 different such numbers:
004, 013, 022, 031, 040, 103, 112, 121, 130, 202, 211, 220, 301, 310, 400.

And I have the following code:

#include <iostream.h> 
using namespace std;

int n,st[100],ok=0, sum;

void afisare()
{
    int s=0;
    for(int i=0;i<n;i++)
       s=s+st[i];
    if (s==sum)
    {
        for(int i=0;i<n;i++)
            cout<<st[i]<<' ';
        cout<<'\n';
        ok++;
    }
}
void back(int k)
{
    int i;
    if(k>n)
       afisare();
    else
       for(i=0;i<10;i++)
       {
        st[k]=i;
        back(k+1);
       }
}

int main()
{
    cout<<"n=";cin>>n;
    cout << "sum= "; cin >> sum;
    back(0);
    cout << endl << endl << ok/10;
    return 0;
}

The problem is that it types each solution exactly 10 times and I can't understand way...What am I doing wrong?

Compile with all warnings and debug info (`g++ -Wall -Wextra -g`). Then **use the debugger** (`gdb`). Read more about [backtracking](https://en.wikipedia.org/wiki/Backtracking) — Basile Starynkevitch, Oct 24 '14 at 08:21
`#include ` seriously? It went obsolete nearly 20 years ago. Get a modern book. — n. m. could be an AI, Oct 24 '14 at 08:49

score 0 · Accepted Answer · edited May 23 '17 at 12:05

These kinds of problems are often easiest to investigate if you consider the most basic cases. Why not trace how many single digit tickets add to a number? It should be just one, right (assuming the number is less than 10, or 0 otherwise)? Well, walk through your code with sum=9 and n=1:

void back(int k)
{
    int i;
    if(k>n)
       afisare();
    else
       for(i=0;i<10;i++)
       {
        st[k]=i;
        back(k+1);
       }
}

When you call back(0) with n = 1, then it will note that 0 is not greater than one. And so it will run through all the digits 0 to 9 and add them and call back(1). Then it will notice in that call that k is 1, and equal to n. So you'll have another loop of tacking on digits... 0 to 10, and bumping k... now to 2. Hence you wind up bottoming out on two digit numbers.

But your sum is only counting n digits, hence the ten times. In short: you are using the comparison k>n, instead of k==n.

So you were "close" in some sense. But there are many other things to be aware of here. #include <iostream.h> won't work in modern compilers, it should just be #include <iostream>. The use of globals is poor form, as is a fixed size array instead of a std::vector:

Arrays vs Vectors: Introductory Similarities and Differences

As a first step, try and rethink this program without the global variables or the fixed size array.

@KeykoYume This related puzzle solution may be of interest (though don't copy the coding style, it was a long time ago): ["Sums of Numbers that add to X"](http://blog.hostilefork.com/summing-numbers-puzzle/) — HostileFork says dont trust SE, Oct 24 '14 at 09:27

Backtracking C++

1 Answers1