nikunjsoni

89

Jul 1st, 2021
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. TC: O(2^n) SC:O(2^n)
  2.  
  3. class Solution {
  4. public:
  5.     vector<int> res;
  6.     vector<int> grayCode(int n) {
  7.         res= {0,1};
  8.         dfs(n);
  9.         return res;
  10.     }
  11.    
  12.     void dfs(int n){
  13.         if(n == 1)
  14.             return;
  15.         dfs(n-1);
  16.         int mask = (1<<(n-1));
  17.         int sz=res.size();
  18.         for(int i=sz-1; i>=0; i--)
  19.             res.push_back(res[i] | mask);
  20.     }
  21.    
  22. };
  23.  
  24. --------------------------------
  25. TC: O(2^n * n) SC:O(2^n)
  26.  
  27. class Solution {
  28. public:
  29.     vector<int> grayCode(int n) {
  30.         vector<int> result;
  31.         result.push_back(0);
  32.         unordered_set<int> isPresent;
  33.         isPresent.insert(0);
  34.         grayCodeHelper(result, n, isPresent);
  35.         return result;
  36.     }
  37.  
  38. private :
  39.     bool grayCodeHelper(vector<int> &result, int n, unordered_set<int> &isPresent) {
  40.         if (result.size() == (1 << n)) return true;
  41.  
  42.         int current = result[result.size() - 1];
  43.         for (int i = 0; i < n; i++) {
  44.             int next = current ^ (1 << i);
  45.             if (isPresent.find(next) == isPresent.end()) {
  46.                 isPresent.insert(next);
  47.                 result.push_back(next);
  48.                 if (grayCodeHelper(result, n, isPresent)) return true;
  49.                 isPresent.erase(next);
  50.                 result.pop_back();
  51.             }
  52.         }
  53.         return false;
  54.     }
  55. };
RAW Paste Data