如何修正递归代码以正确生成所有非空字母序列

原代码的核心问题是没实现全排列逻辑——它只是按原字符串顺序生成子序列，还允许重复选取同一位置的字符，同时误把空字符串也加入了结果。要生成所有非空的全排列序列，得换一种递归思路：每次从所有未使用的字符里选一个，加入当前序列，递归处理剩余字符，最后回溯取消标记。

基础版本（适用于无重复字符输入，如"ABC"） #

import java.util.HashSet;
import java.util.Set;

public class PermutationGenerator {
    public static void main(String[] args) {
        String tiles = "ABC";
        Set<String> ans = new HashSet<>();
        boolean[] used = new boolean[tiles.length()];
        solve(tiles, used, "", ans);
        // 打印所有非空全排列序列
        ans.forEach(System.out::println);
    }

    public static void solve(String tiles, boolean[] used, String output, Set<String> ans) {
        // 仅将非空序列加入结果集
        if (!output.isEmpty()) {
            ans.add(output);
        }

        for (int i = 0; i < tiles.length(); i++) {
            if (!used[i]) {
                // 标记当前字符已被使用
                used[i] = true;
                // 递归生成包含当前字符的序列
                solve(tiles, used, output + tiles.charAt(i), ans);
                // 回溯：取消标记，让该字符可被其他分支使用
                used[i] = false;
            }
        }
    }
}

关键改动说明 #

• 新增boolean[] used数组：标记字符是否已被选入当前序列，避免重复选取同一位置的字符。
• 循环从i=0开始：每次递归遍历所有未使用的字符，实现全排列（支持打乱原字符串顺序的组合）。
• 非空判断：仅当output不为空时才加入结果集，符合题目要求。
• 回溯操作：递归返回后重置used[i]，保证字符能被其他递归分支复用。

去重版本（适用于含重复字符的输入，如"AAB"） #

如果输入字符串有重复字符，上面的代码会生成重复序列。可以先排序字符串，再跳过重复分支来优化：

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class PermutationGenerator {
    public static void main(String[] args) {
        String tiles = "AAB";
        // 先排序字符，让相同字符相邻，方便去重
        char[] chars = tiles.toCharArray();
        Arrays.sort(chars);
        String sortedTiles = new String(chars);
        
        Set<String> ans = new HashSet<>();
        boolean[] used = new boolean[sortedTiles.length()];
        solve(sortedTiles, used, "", ans);
        
        ans.forEach(System.out::println);
    }

    public static void solve(String tiles, boolean[] used, String output, Set<String> ans) {
        if (!output.isEmpty()) {
            ans.add(output);
        }

        for (int i = 0; i < tiles.length(); i++) {
            // 跳过已使用的字符，或跳过重复且前一个相同字符未被使用的分支（避免重复序列）
            if (used[i] || (i > 0 && tiles.charAt(i) == tiles.charAt(i-1) && !used[i-1])) {
                continue;
            }
            used[i] = true;
            solve(tiles, used, output + tiles.charAt(i), ans);
            used[i] = false;
        }
    }
}

去重逻辑说明 #

• 先排序字符串，让相同字符相邻。
• 循环中跳过重复分支：当当前字符与前一个字符相同，且前一个字符未被使用时，说明前一个相同字符的分支已经覆盖了当前字符的所有可能情况，直接跳过即可避免生成重复序列。

内容的提问来源于stack exchange，提问作者Rahul A