如何生成包含重复字符字符串的所有不重复子序列-java教程-PHP中文网

如何生成包含重复字符字符串的所有不重复子序列

本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归+集合去重方案，通过 HashSet 自动过滤重复结果，并避免在递归过程中做低效的线性查找。

本文介绍在字符串含重复字符时，高效生成所有唯一子序列的递归+集合去重方案，通过 `hashset` 自动过滤重复结果，并避免在递归过程中做低效的线性查找。

生成字符串的所有非重复子序列（distinct subsequences）是经典回溯问题。当输入字符串含重复字符（如 "ggg" 或 "aba"）时，朴素递归会大量生成相同子序列（如多次生成 "g" 或 "a"），导致结果冗余。关键在于：去重不应发生在递归返回后逐个检查 contains()（时间复杂度高且易出错），而应在结果汇聚层统一处理，或在递归前剪枝。

最简洁、鲁棒的解法是使用 Set 作为最终容器，在递归完成后再统一收集——这正是 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 个）
    }
}</string></string></string>

✅ 关键要点说明：