help with backtracking

[E3h7X9L8]

read n numbers and a number a .generate all possible numbers from numbers n lesser than a

example: for 0,2,3 and a=300; 20,200,220,202,300,302,322 etc

[keskiverto]

Please note, that this is not a homework site. We won't do your homework for you. The purpose of homework is that you learn by doing. However we are always willing to help solve problems you encountered, correct mistakes you made in your code and answer your questions.

We didn't see your attempts to solve this problem yourself and so we cannot correct mistakes you didn't made and answer questions you didn't ask. To get help you should do something yourself and get real problems with something. If your problem is "I don't understand a thing", then you should go back to basics and study again.


You say: "read n numbers". Is that n numbers or n digits?

The problem seems to be combinatorics, enumeration of combinations.

[E3h7X9L8]

yeah sorry , about that , i dont even know how to start , i tried storing the n digits in a array , then i did a recursive backtracking algorithm to get every combination of that array numbers , but the problem is i need to display only the good answers ... and i dont know how to verify them if they are good and i dont know either how to display the numbers with less digits than the array length (in my example on my actual code if i enter 0 2 3 i would get every combinations of 0 2 3 , but not 23 or 32 or only 3 ...)

here is my code

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

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

void backt(int i, int n,int m)
{
   int j;
   if (m == n)
     afis(n);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a[i]), a[j]);
          backt(i+1, n , m + i);
          swap((a[i]), a[j]);//backtrack
       }
   }
}


int main()
{
  int n;
  cout << "Value numbers: " ;cin>>n;
   for(int i = 1; i <= n; i++)
    {
        cout << "Value " << i << " is: "; cin >> a[i];
    }
  cout << "Number "; cin >> s;
  backt(1,n,0);
}

[anup30]

_{leryss wrote:}

and i dont know how to verify them

you have to make number to compare;

i.e. if one combination(permutation actually) is this:
a[0]=3; a[1]=2; a[2]=0;
then the number:
int number = a[2]*1 + a[1]*10 + a[0]*100;

then, if(number <s ) > print it.

[E3h7X9L8]

ty for help i did it :D

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

void afis(int k)
{

        for(int i = 1; i <= k; i++)
        cout << sol[i] << " ";
        cout << endl;
}

bool validate(int k)
{
    int number = 0;
    for(int j = 1; j <= k; j++)
    {
        number = number * 10 + sol[j];
    }
    if(number < s)
        return true;
    else
        return false;
}
void backt(int i, int maxP, int length)
{
    if(validate(i - 1) && sol[1] != 0)
        afis(i-1);
    for(int j = 1; j <= length - maxP; j++)
    {
        sol[i] = a[j];
        backt(i + 1, maxP * 10 + a[i], length);
        maxP = 0;
    }
}


int main()
{
  int n;
  cout << "Value of numbers: " ;cin>>n;
   for(int i = 1; i <= n; i++)
    {
        cout << "Value " << i << " is: "; cin >> a[i];
    }
  cout << "Number to compare "; cin >> s;
  backt(1,0,n);
}