mickypinata

LEET-T0060: Permutation Sequence

Dec 1st, 2021
576
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 9 + 5;
  5.  
  6. string str;
  7. int cnt;
  8. bool visited[N];
  9.  
  10. bool recur(int n, int k, int i){
  11.     if(i == 0){
  12.         ++cnt;
  13.         if(cnt == k){
  14.             return true;
  15.         }
  16.         return false;
  17.     }
  18.     for(int j = 0; j < n; ++j){
  19.         if(!visited[j]){
  20.             str += (char)j + 1 + '0';
  21.             visited[j] = true;
  22.             if(recur(n, k, i - 1)){
  23.                 return true;
  24.             }
  25.             str.pop_back();
  26.             visited[j] = false;
  27.         }
  28.     }
  29.     return false;
  30. }
  31.  
  32. string getPermutation(int n, int k){
  33.     if(recur(n, k, n)){
  34.         return str;
  35.     }
  36.     return "";
  37. }
  38.  
  39. int main(){
  40.  
  41.     int n, k;
  42.     scanf("%d%d", &n, &k);
  43.     cout << getPermutation(n, k);
  44.  
  45.     return 0;
  46. }
  47.  
RAW Paste Data