生成字符串中所有不重复的子序列（含重复字符处理）-java教程-PHP中文网

本文介绍如何高效生成含重复字符字符串的所有唯一子序列，避免暴力递归+列表查重导致的性能与逻辑缺陷，核心方案是使用 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"
    }
}</string></string></string></string>

? 关键设计说明：

new String(op, 0, j) 确保只转换已写入的有效前缀，避免末尾残留字符；
HashSet 的 add() 操作平均 O(1)，总时间复杂度为 O(2ⁿ × L)，空间复杂度 O(2ⁿ × L)，这是该问题的理论最优解之一；
若需按字典序输出，可对最终 Set 调用 new TreeSet(result) 或 result.stream().sorted().collect(...)。

⚠️ 注意事项：