先提一句：从代码逻辑来看，两种算法实际是生成左右两侧字符和相等的二进制字符串（可能你描述的“无连续1”是笔误？不过我们还是基于给定的代码来做复杂度分析）。

1. 你的实现：暴力回溯+事后校验 #

思路拆解 #

这是很直观的暴力回溯思路：先穷举所有长度为k的二进制字符串（每个位置依次尝试填0或1），等整个字符串生成完毕后，再通过check函数校验左右两半的字符和是否相等，符合条件才输出结果。

时间复杂度 #

• 回溯阶段：每个位置有2种选择，总共有2^k个可能的二进制串，这是最大的时间开销。
• 校验阶段：每个串生成后，check函数需要遍历约k个字符计算左右和，所以这部分的时间是O(k * 2^k)。
• 整体时间复杂度：O(k * 2^k)——因为线性的校验操作嵌套在指数级的回溯次数里，随着k增大，这个开销会爆炸式增长。

空间复杂度 #

• 递归栈：回溯的递归深度是k（从index=0到index=k），栈空间占用是O(k)。
• 辅助数组：用来存当前二进制串的char[] binary，大小也是k，属于O(k)的空间。
• 整体空间复杂度：O(k)，主要由递归栈和辅助数组占据。

2. 网站的实现：定向回溯+提前剪枝 #

思路拆解 #

这个实现聪明多了，是带剪枝的定向回溯：从字符串的两端向中间构建，用di变量跟踪左右两侧的字符和差值，同时提前判断剩余长度是否还能把差值拉回0（也就是2*Math.abs(di) <=n这个条件），如果不可能就直接终止这条分支，完全避免无效的递归。

时间复杂度 #

• 递归分支数：因为有剪枝，不会遍历所有2^n种可能。它只生成符合条件的字符串，时间开销直接等于符合条件的字符串数量S，而S远小于2^n（比如n=5时，符合条件的只有4个，总共有32种可能）。
• 每个递归步骤都是O(1)的字符串拼接（虽然Java里字符串是不可变的，拼接会产生临时对象，但复杂度分析看量级的话，这部分可以忽略）。
• 整体时间复杂度：O(S)，其中S是结果集的大小，比你的实现效率高几个量级。

空间复杂度 #

• 递归栈：递归深度是n/2（每次递归n减少2，直到n=0或1），栈空间是O(n)。
• 字符串临时空间：每次递归会生成新的left和right字符串，最大长度是n/2，这部分也是O(n)。
• 整体空间复杂度：O(n)，和你的实现处于同一量级，但实际递归深度更浅（n/2 vs k）。不过要注意，Java里字符串拼接会产生更多临时对象，实际内存开销可能略高于你的char数组实现，但复杂度量级是一致的。

孰优孰劣？ #

• 时间上：网站的实现碾压你的实现。你的暴力思路是“先全生成再筛选”，指数级带线性因子的开销；而网站的实现是“只生成有效结果”，时间和结果集大小成正比，效率高太多。
• 空间上：两者复杂度量级相同，但你的实现用char数组复用空间，实际内存占用会略低一点；网站的实现递归深度更浅，但字符串拼接的临时对象会多一些，整体打个平手。

内容的提问来源于stack exchange，提问作者ANSHUMAN MISHRA