华为OD机试 - 全排列 - 回溯（Java 2024 C卷 100分）

ゝ一纸荒年。 2024-04-17 10:28 16阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

给定一个只包含大写英文字母的字符串S，要求你给出对S重新排列的所有不相同的排列数。

如：S为ABA，则不同的排列有ABA、AAB、BAA三种。

### 二、输入描述 ###

输入一个长度不超过10的字符串S，确保都是大写的。

### 三、输出描述 ###

输出S重新排列的所有不相同的排列数（包含自己本身）。

#### 1、输入 ####

ABA

#### 2、输出 ####

#### 3、说明 ####

### 四、解题思路 ###

全排列是一个很经典的回溯算法，定义一个Deque，存储使用了的字母，通过回溯寻找符合要求的字符串。

### 五、Java算法源码 ###

public class Test01 {
        
        // 可能的组合
        private static Set<List<String>> lists = new HashSet<>();
    
        public static void main(String[] args) {
        
            Scanner sc = new Scanner(System.in);
            String input = sc.nextLine();
            // 使用了的字母
            Deque<String> deque = new ArrayDeque<>();
            // 字母是否使用过
            boolean[] used = new boolean[input.length()];
            dfs(input, used, 0, deque); // 递归每一层
            System.out.println(lists.size());
        }
    
        /**
         * 通过回溯寻找符合要求的字符串
         *
         * @param input 若干个字符
         * @param used  字符是否使用过
         * @param j     遍历到第j个字符
         * @param deque 使用了的字母
         */
        public static void dfs(String input, boolean[] used, int j, Deque<String> deque) {
        
            if (j == input.length()) {
        
                // 符合要求的字符串集合
                lists.add(new ArrayList<>(deque));
                return;
            }
    
            for (int i = 0; i < input.length(); i++) {
        
                // 如果使用过，则跳出
                if (used[i]) {
        
                    continue;
                }
    
    
                if (i > 0 && input.charAt(i) == input.charAt(i - 1) && !used[i - 1]) {
        
                    continue;
                }
    
                deque.addLast(input.charAt(i) + "");
                used[i] = true;
                // 通过回溯寻找符合要求的字符串
                dfs(input, used, j + 1, deque);
                deque.removeLast();
                used[i] = false;
            }
        }
    }

### 六、效果展示 ###

#### 1、输入 ####

ABCDEFGHHA

#### 2、输出 ####

907200

#### 3、说明 ####

![在这里插入图片描述][eb37f556f97845f898fa4b289504fb93.png_pic_center]

🏆下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

🏆本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/421b7e685f9542599813d2311bd8df78.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[eb37f556f97845f898fa4b289504fb93.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/a0e6641b8b90470ca3864c9a0afb659e.png
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/987e34c57c8540f081dd101f2d709d98.gif