ValerianBenchea

BACKTRACKING Problema parantezelor corectecte

Oct 6th, 2021
1,078
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int x[101], n;
  5.  
  6. void tipar()
  7. {
  8.     for(int i=1; i<=n; i++)
  9.     {
  10.         if(x[i]==0)
  11.             cout<<'('<<' ';
  12.         else
  13.             cout<<')'<<' ';
  14.     }
  15.     cout<<'\n';
  16.  
  17. }
  18.  
  19. bool e_bun(int k)
  20. {
  21.     int cated=0, catei=0;
  22.     for(int i=1; i<=k; i++)
  23.         if(x[i]==0)
  24.             cated++;
  25.         else
  26.             catei++;
  27.     if(cated>n/2)
  28.         return 0;
  29.     if(cated<catei)
  30.         return 0;
  31.     return 1;
  32. }
  33.  
  34. void back()
  35. {
  36.     int k=1;
  37.     x[k]=-1;
  38.     while(k>0)
  39.     {
  40.         if(x[k]<1)
  41.         {
  42.             x[k]++;
  43.             if(e_bun(k))
  44.                 if(k==n)
  45.                     tipar();
  46.                 else
  47.                 {
  48.                     k++;
  49.                     x[k]=-1;
  50.                 }
  51.         }
  52.         else
  53.             k--;
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59.     cin>>n;
  60.     back();
  61.     return 0;
  62. }
  63.  
Advertisement
Add Comment
Please, Sign In to add comment