喜欢我的暴搜吗 ^^
/*
 * @lc app=leetcode.cn id=3211 lang=cpp
 *
 * [3211] 生成不含相邻零的二进制字符串
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
 public:
  vector<string> validStrings(int n) {
    vector<string> ans;
    auto check = [&](string s) {
      int len = s.length();
      if (len <= 1) return true;
      int cnt = 0;
      if (s[0] == '0' && s[1] == '0') return false;
      if (s[len - 1] == '0' && s[len - 2] == '0') return false;
      for (int i = 1; i < len - 1; ++i) {
        if (s[i] == '0' && s[i - 1] == '0') return false;
        if (s[i] == '0' && s[i + 1] == '0') return false;
      }
      return true;
    };
    auto dfs = [&](auto&& self, string s) {
      if (s.length() > n) return;
      if (s.length() == n && check(s)) {
        ans.push_back(s);
        return;
      } else {
        self(self, s + "0");
        self(self, s + "1");
      }
    };
    dfs(dfs, "0");
    dfs(dfs, "1");
    return ans;
  }
};
// @lc code=end