Advertisement
monyca98

combinari backtracking

May 27th, 2016
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.03 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. int succesor(int st[20],int n,int m,int k)
  4. {   if(st[k]<n-m+k)
  5.     {   st[k]++;
  6.         return 1;
  7.     }
  8.     else
  9.         return 0;
  10. }
  11. int valid(int st[20],int k)
  12. {   for(int i=1;i<k;i++)
  13.         if(st[k]==st[i])
  14.             return 0;
  15.     return 1;
  16. }
  17. int tipar(int st[20],int m)
  18. {   for(int i=1;i<=m;i++)
  19.         cout<<st[i];
  20.     cout<<endl;
  21. }
  22. void bt(int n,int m,int k,int st[20])
  23. {   int as,ev;
  24.     k=1;
  25.     if(k==1)
  26.         st[k]=0;
  27.     else
  28.         st[k]=st[k-1];
  29.     while(k>0)
  30.     {   as=1;
  31.         ev=0;
  32.         while(as && !ev)
  33.         {   as=succesor(st,n,m,k);
  34.             if(as)
  35.                 ev=valid(st,k);
  36.         }
  37.         if(as)
  38.             if(k==m)
  39.                 tipar(st,m);
  40.             else
  41.             {   k++;
  42.                 if(k==1)
  43.                     st[k]=0;
  44.                 else
  45.                     st[k]=st[k-1];
  46.              }
  47.         else
  48.             k--;
  49.     }
  50. }
  51. int main()
  52. {   int n,k,st[20],m;
  53.     cin>>n>>m;
  54.     bt(n,m,k,st);
  55.  
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement