本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归+集合去重方案，通过 HashSet 自动过滤重复结果，并避免在递归过程中做低效的线性查找。
本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归+集合去重方案，通过 `hashset` 自动过滤重复结果，并避免在递归过程中做低效的线性查找。
生成字符串的所有非重复子序列（distinct subsequences）是经典回溯问题。当输入字符串含重复字符（如 "ggg" 或 "aba"）时，朴素递归会大量生成相同子序列（如多次生成 "g" 或 "a"），导致结果冗余。关键在于：去重不应发生在递归返回后逐个检查 contains()（时间复杂度高且易出错），而应在结果汇聚层统一处理，或在递归前剪枝。
最简洁、鲁棒的解法是使用 Set<String> 作为最终容器，在递归完成后再统一收集——这正是 GeeksforGeeks 提供的参考实现的核心思想。其优势在于：
- 利用 HashSet 的 O(1) 平均插入与自动去重能力；
- 无需修改递归逻辑，保持分治清晰性；
- 避免在每层递归中调用 list.contains()（每次为 O(n)，整体退化至 O(2^N × N)）。
以下是优化后的完整 Java 实现（含注释与可运行结构）：
import java.util.*;
public class DistinctSubsequences {
// 主入口：返回所有不重复子序列的列表
public static List<String> generateDistinct(String s) {
Set<String> result = new HashSet<>();
char[] chars = s.toCharArray();
char[] output = new char[chars.length]; // 缓存当前构建的子序列
generateHelper(chars, output, 0, 0, result);
return new ArrayList<>(result);
}
// 递归回溯生成所有子序列，结果存入 set 自动去重
private static void generateHelper(char[] input, char[] output,
int i, int j, Set<String> result) {
// 基础情况：已遍历完输入字符串
if (i == input.length) {
// 截取 output 中有效部分（长度为 j），转为字符串并加入集合
result.add(new String(output, 0, j));
return;
}
// 分支1：选择当前字符 → 放入 output[j]，j+1
output[j] = input[i];
generateHelper(input, output, i + 1, j + 1, result);
// 分支2：不选择当前字符 → j 不变
generateHelper(input, output, i + 1, j, result);
}
// 示例用法
public static void main(String[] args) {
System.out.println(generateDistinct("aba"));
// 输出可能为：[, a, b, ab, aa, aba, ba]（顺序不定，无重复）
System.out.println(generateDistinct("ggg"));
// 输出：[, g] —— 仅空串和单个 "g"，共 2 个（而非 2³=8 个）
}
}✅ 关键要点说明：
- output 数组按索引 j 动态记录当前子序列字符，new String(output, 0, j) 精确截取有效长度，避免 \0 干扰；
- Set<String> 在最终汇总层统一去重，逻辑清晰、性能稳定；
- 空子序列 "" 自然被包含（当全程不选任何字符时，j==0，new String(output,0,0) 返回空串）；
- 时间复杂度为 O(2^N)（生成总数） × O(N)（字符串构造），空间复杂度 O(2^N × N)（存储所有唯一子序列）。
⚠️ 注意事项：
- 若需按字典序或长度排序输出，可在返回前对 ArrayList 调用 Collections.sort()；
- 对超长字符串（N > 20），因子序列数呈指数增长，应考虑改用迭代动态规划统计数量（如 GeeksforGeeks 的计数方案），而非枚举全部；
- 此方法不依赖字符排序，适用于任意 Unicode 字符串。
该方案以“空间换逻辑简洁性”，是教学与工程实践中平衡可读性、正确性与维护性的优选解。
