题目：
给你一个正整数 n。如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。
示例 1：
输入： n = 3
输出： [“010”,”011”,”101”,”110”,”111”]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。
示例 2：
输入： n = 1
输出： [“0”,”1”]
解释：
长度为 1 的有效字符串有："0" 和 "1"。
提示：
1 <= n <= 18
思路：
回溯算法：总共的长度为 n 的字符串有 2^n 个，所以我们通过回溯寻找所有满足条件的字符串即可。每个位置以下面的规则进行填充：
如果前一个字符为 '0'，那么这个字符只能填 '1'
如果前一个字符为 '1'，那么这个字符就可以填两种情况
由于要判断前一个字符，那么对于第一个字符，就要特殊处理
代码：
class Solution {
public:
string str;
vector<string> ans;
void backTrack(int n) {
if (str.size() == n) {
ans.push_back(str);
return;
}
if (str[str.size() - 1] == '0') {
str.push_back('1');
backTrack(n);
str.erase(str.end() - 1);
return;
}
str.push_back('0');backTrack(n);str.erase(str.end() - 1);
str.push_back('1');backTrack(n);str.erase(str.end() - 1);
}
vector<string> validStrings(int n) {
if (n == 1) return {"0", "1"};
str.push_back('0');
backTrack(n);
str = "1";
backTrack(n);
return ans;
}
};