getting unexpected and weird output

[E3h7X9L8]

So I had to make this backtracking app, and I decided to make it also recursive, the app must do this:
"User inputs N numbers , then a S number , generate all possible numbers created from the N numbers lesser than S
i.e: For user input N = 3(0,2,3) and S = 300 the app will generate 2 < 300, 20 < 200 , 203 < 300 , 222 < 300 etc."

The application works for inputs > 0, but when i put 0 as input , the whole screen will be filled with 0's and the app will crash, I dont really understand why...

#include<iostream>
#include<windows.h>
using namespace std;
int s,a[20],sol[20];

void afis(int k) // prints solution
{
    for(int i = 1; i <= k; i++)
        cout << a[sol[i]] << " ";
    cout << endl;
}

bool validate(int k) // checking if the solution is less than S
{
    int number = 0;
    for(int j = 1; j <= k ; j++)
    {
        number = number * 10 + a[sol[j]];
    }
    if(number < s)
        return true;
    else
        return false;

}
void backt(int index, int lung) // generates solution
{
    afis(index - 1);
    for(int i = 1; i <= lung; i++)
        if(validate(index))
    {
        sol[index] = i;
        backt(index + 1, lung);
    }
}

int main()
{
  int n;
  cout << "Numar valori cifre: " ;cin>>n;
   for(int i = 1; i <= n; i++)
    {
        cout << "Valoarea cifrei " << i << " este: "; cin >> a[i];
    }
  cout << "Numar: "; cin >> s;
  backt(1,n);

  cin.ignore(1, ' ');
}

[keskiverto]

That looks complicated, as in difficult to follow, debug, maintain, etc.

It definitely has undefined behaviour, because the first call to backt() calls first afis(), which dereferences uninitialized sol.


How about nonrecursive:

1. Store digits in ordered container D.
2. Calculate how many digit positions is in S.
3. For each position* in S iterate over D. A combination is X.
4. Append each valid X into std::set R.
5. Show R.

[*] you could limit the most significant digits prefixes to <= of the prefix of S.

[E3h7X9L8]

well thanks for help , i figured it out before seeing your post , when inputing 0 , the index was overflowing the array with integers i solved that by putting a if(index > lung) with a break statement in the for of the generation function... now works like wonders , btw i forgot to tell that i wanted to be efficient and thats why i did not used a iterative version

[keskiverto]

You are right, the recursion is simpler.

Here is some obfuscation though:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

void bar( int num, std::vector<int> & pref ) {
    while ( num ) {
        pref.push_back( num );
        num /= 10;
    }
    if ( pref.empty() ) pref.push_back( 0 );
}

void foo( const std::vector<int> & dig, size_t pos,
          const std::vector<int> & pre, int sum ) {
    std::cout << "foo ";
    if ( pos > 0 ) {
        for ( auto y : dig ) {
            int sumx = 10 * sum + y;
            if ( sumx <= pre[pos-1] )
                foo( dig, pos-1, pre, sumx );
            else return;
        }
    } else {
        if ( sum < pre[0] ) std::cout << sum << '\n';
    }
}

int main()
{
    std::vector<int> digits { 0, 7, 3 };
    std::sort( std::begin( digits ), std::end( digits ) );
    assert( ! digits.empty() );
    assert( 0 <= digits.front() );
    assert( digits.back() < 10 );

    for ( auto x : digits ) std::cout << x << ' ';
    std::cout << "digits\n";
    
    int S = 325;

    std::vector<int> prefix;
    prefix.reserve( 3 );
    bar( S, prefix );
    for ( auto x : prefix ) std::cout << x << ' ';
    std::cout << "prefix\n\n";

    auto count = prefix.size();    
    foo( digits, count, prefix, 0 ); 
    
    return 0;
}