本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归回溯方法，核心是利用 Set 自动去重，并通过字符数组+临时缓冲区避免字符串频繁拼接，兼顾正确性与可读性。
本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归回溯方法，核心是利用 `set` 自动去重，并通过字符数组+临时缓冲区避免字符串频繁拼接，兼顾正确性与可读性。
要生成含重复字符字符串的所有非重复子序列（distinct subsequences），关键在于避免因相同字符在不同位置被多次选取而产生语义相同的子序列（如 "gg" 中两个 'g' 产生的 "g" 子序列不应重复出现）。直接在递归返回后用 ArrayList.contains() 检查去重不仅效率极低（O(n) 每次查找），更因递归分支交错导致逻辑失效——正如提问中第二个函数所示，current.contains(p) 在局部 ArrayList 上调用，无法跨分支共享状态，故无法真正拦截重复。
推荐做法是自顶向下递归 + 全局去重容器：使用 Set
以下为优化实现（已重构为清晰、可复用的静态方法）：
import java.util.*;
public class DistinctSubsequences {
public static Set<String> generateDistinct(String s) {
Set<String> result = new HashSet<>();
char[] chars = s.toCharArray();
char[] buffer = new char[chars.length]; // 缓冲区，避免字符串拼接开销
generateHelper(chars, buffer, 0, 0, result);
return result;
}
private static void generateHelper(char[] chars, char[] buffer,
int idx, int len, Set<String> result) {
// 基础情况：处理完所有字符
if (idx == chars.length) {
result.add(new String(buffer, 0, len)); // 只取有效长度部分
return;
}
// 分支1：包含当前字符
buffer[len] = chars[idx];
generateHelper(chars, buffer, idx + 1, len + 1, result);
// 分支2：不包含当前字符
generateHelper(chars, buffer, idx + 1, len, result);
}
// 使用示例
public static void main(String[] args) {
String input = "ggg";
Set<String> subs = generateDistinct(input);
System.out.println("Total distinct subsequences: " + subs.size());
System.out.println("All subsequences: " + new ArrayList<>(subs));
// 输出示例（顺序不定）: [ , g, gg, ggg]
}
}✅ 关键设计说明：
- buffer 数组替代字符串拼接：每次递归仅写入单个字符到固定位置，len 记录当前子序列长度，最终 new String(buffer, 0, len) 构造结果，时间复杂度从 O(L²) 降至 O(L)，L 为子序列长度；
-
Set
全局去重 ：所有递归路径最终都向同一 Set 添加，天然消除重复，无需额外状态传递或回溯检查； - 无剪枝亦正确：即使输入含大量重复（如 "aaaa"），算法仍能准确生成全部 5 个子序列（"", "a", "aa", "aaa", "aaaa"），因为 Set 会合并所有等价字符串。
⚠️ 注意事项：
- 若需按字典序或长度排序输出，应在最终返回前对 Set 转为 List 并排序（new ArrayList(result).sort(Comparator.naturalOrder())）；
- 对超长字符串（|s| > 20），指数级子序列数量（最坏 2ⁿ）可能导致内存溢出，此时应改用动态规划统计总数（如 GeeksforGeeks 中的 countDistinctSubsequences），而非枚举全部；
- 此解法不依赖字符排序，适用于任意 Unicode 字符串。
该方案以简洁的递归结构、标准库工具的合理运用，兼顾了正确性、可维护性与运行效率，是解决“重复字符下唯一子序列生成”问题的经典实践。
