leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1718.cpp (898B)

      1 class Solution {
      2     bool seen[21] = {0};
      3     vector<int> res = vector(39, 0);
      4 
      5     bool rec(const int n, int crnt) {
      6         while (crnt < size(res) && res[crnt])
      7             crnt++;
      8         if (crnt == size(res)) return true;
      9 
     10         for (int i = n; i > 1; i--) {
     11             if (seen[i] || crnt + i >= size(res) || res[crnt + i]) continue;
     12             res[crnt + i] = res[crnt] = i;
     13             seen[i] = true;
     14             if (rec(n, crnt + 1)) return true;
     15             seen[i] = false;
     16             res[crnt + i] = 0;
     17         }
     18 
     19         if (!seen[1]) {
     20             res[crnt] = 1;
     21             seen[1] = true;
     22             if (rec(n, crnt + 1)) return true;
     23             seen[1] = false;
     24         }
     25         res[crnt] = 0;
     26 
     27         return false;
     28     }
     29 
     30   public:
     31     vector<int> constructDistancedSequence(const int n) {
     32         res.resize(2 * n - 1);
     33         rec(n, 0);
     34         return res;
     35     }
     36 };