本文介绍如何高效生成含重复字符字符串的所有唯一子序列，避免暴力递归+列表查重导致的性能与逻辑缺陷，核心方案是使用 Set 自动去重，并结合回溯式字符选择递归实现。
本文介绍如何高效生成含重复字符字符串的所有唯一子序列，避免暴力递归+列表查重导致的性能与逻辑缺陷，核心方案是使用 set
在处理含重复字符的字符串（如 "ggg" 或 "aba"）时，直接套用标准子序列生成逻辑会导致大量重复结果——例如 "a" 可能被多次生成，仅因它来自不同位置的相同字符。你尝试在递归基例中用 current.contains(p) 判断去重，但该方式存在两个根本问题：
- 时机错误：去重逻辑嵌入在单次递归分支内（如 left 或 right），而重复子序列可能分别产生于左右两支，彼此不可见；
- 效率灾难：每次插入前遍历整个列表，时间复杂度升至 O(2ⁿ × L)，L 为平均子序列长度，完全不可扩展。
✅ 正确解法是分离“生成”与“去重”职责：
- 使用 Set
作为统一容器，天然保证唯一性； - 采用固定长度字符数组 op[] 构建当前子序列，通过索引 j 精确控制写入位置；
- 递归过程不返回列表，而是直接向共享集合 sn 添加结果，消除分支合并开销。
以下是优化后的完整实现：
import java.util.*;
public class DistinctSubsequences {
// 主入口：返回所有不重复子序列的集合
public static Set<String> generateDistinct(String s) {
Set<String> result = new HashSet<>();
char[] chars = s.toCharArray();
char[] output = new char[chars.length + 1]; // +1 for '\0' terminator
subsequences(result, chars, output, 0, 0, chars.length);
return result;
}
// 回溯递归：i=当前处理字符索引，j=输出数组写入位置
private static void subsequences(Set<String> result,
char[] s,
char[] op,
int i,
int j,
int n) {
if (i == n) {
op[j] = '\0'; // 结束符标记字符串边界
result.add(new String(op, 0, j)); // 仅截取有效长度 [0, j)
return;
}
// 选择当前字符：放入op[j]，j+1
op[j] = s[i];
subsequences(result, s, op, i + 1, j + 1, n);
// 不选当前字符：j不变
subsequences(result, s, op, i + 1, j, n);
}
// 示例用法
public static void main(String[] args) {
String input = "aba";
Set<String> subs = generateDistinct(input);
System.out.println("Input: \"" + input + "\"");
System.out.println("Distinct subsequences (" + subs.size() + "):");
subs.stream().sorted().forEach(System.out::println);
// 输出: "", "a", "aa", "ab", "aba", "b", "ba"
}
}? 关键设计说明：
- new String(op, 0, j) 确保只转换已写入的有效前缀，避免末尾残留字符；
- HashSet 的 add() 操作平均 O(1)，总时间复杂度为 O(2ⁿ × L)，空间复杂度 O(2ⁿ × L)，这是该问题的理论最优解之一；
- 若需按字典序输出，可对最终 Set 调用 new TreeSet(result) 或 result.stream().sorted().collect(...)。
⚠️ 注意事项：
- 此方法仍会生成空字符串 ""（即不选任何字符），若业务要求排除，请在添加前判断 j > 0；
- 对超长字符串（|s| > 25），子序列数量呈指数级增长（最坏 2ⁿ），需评估内存与运行时限制；
- 如需进一步优化（如跳过相邻重复字符剪枝），可先对字符排序后加入“同层去重”逻辑，但会改变原始顺序语义，慎用。
该方案简洁、健壮、符合工程实践，是解决“含重字符字符串唯一子序列生成”问题的标准范式。
