YEZAELP

LeetCode: Permutations

Dec 1st, 2021 (edited)
653
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /// Backtracking
  2. class Solution {
  3. public:
  4.    
  5.     vector < vector <int> > ans;
  6.     int ar[6 + 10];
  7.     int n;
  8.    
  9.     void f(int l, int r){
  10.         if(l == r){
  11.             vector <int> cur;
  12.             for(int i=0;i<n;i++) cur.push_back(ar[i]);
  13.             ans.push_back(cur);
  14.             return;
  15.         }
  16.         for(int i=l;i<=r;i++){
  17.             swap(ar[l], ar[i]);
  18.             f(l + 1, r);
  19.             swap(ar[l], ar[i]);
  20.         }
  21.     }
  22.    
  23.     vector<vector<int>> permute(vector<int>& nums) {
  24.         n = nums.size();
  25.         for(int i=0;i<n;i++) ar[i] = nums[i];
  26.         f(0, n-1);
  27.         return ans;
  28.     }
  29. };
  30.  
  31. /// std::next_permutation
  32. class Solution {
  33. public:
  34.    
  35.     vector<vector<int>> permute(vector<int>& nums) {
  36.         vector < vector <int> > ans;
  37.         sort(nums.begin(), nums.end()); /// ***
  38.         do{
  39.             ans.push_back(nums);
  40.         }while(next_permutation(nums.begin(), nums.end()));
  41.         return ans;
  42.     }
  43. };
RAW Paste Data