地址：

1718. 构建字典序最大的可行序列

状态：未AC

代码：回溯

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