算法题--所有排列组合

> 华为OD机试最后一题

### 题目描述：

输入一个数字N，然后输入一个长度为N的字符数组。求字符数组的所有不重复的排列组合，并对其字典序升序排序。

例如：

输入 3，然后输入 "a b c"
则输出：
abc
acb
bac
bca
cab
cba

输入 3，然后输入"a ab b"
则输出：
aabb
abab
abba
baab
baba

### 思路：

这道题初看起来比较简单，但是实际不是一道很简单的遍历题目。需要用到动态规划的思想。分析题目意思是想得到长度为n的字符数组所有元素不重复的排列组合，并且升序排序输出。

那么结果可以先确定是存在一个TreeSet集合中，每次组合到的字符串存入TreeSet中，一下就解决了“不重复”和“升序排序”两个问题。

其次，要求当前字符数组的所有排列组合，则可以求比当前字符串数组少一个字符串的子字符串数组的所有排列组合，然后加上当前字符串。

比如：要求"a" "b"的所有排列组合；可以先按住"a"，求子字符串数组"b"的所有排列组合；"b"只有一个元素，可以直接求得排列组合结果只有一种："b"。然后拿当前字符"a"与子字符数组"b"的结果求排列组合。那结果可以分为两大类：1、将当前字符串"a"放到子字符数组结果的每一项元素的前面；2、将当前字符串"a"放到子字符数组结果的每一项元素的后面；所以求得"a" "b"这个字符数组的所以排列组合为"ab"和"ba"。将结果存入TreeSet集合中。
上面是按住"a"的，接着要按住"b"，求子字符串数组"a"的所有排列组合。步骤和上面一样。

### 代码：

```java
package com.example.demo.HuaweiOC;

import java.util.*;

/**
 * @author: HanXu
 * on 2022/2/18
 * Class description: 输入一个数字N，然后输入一个长度为N的字符数组。求字符数组的所有不重复的排列组合，并升序排序输出。
 */
public class Demo3 {
    public static void main(String[] args) {
        int n = 3;
        String[] arrStr = {"a", "ab", "b"};
        String[] resultStrArr = findAllCombinations(n, arrStr);
        System.out.println(Arrays.toString(resultStrArr));
        //[aabb, abab, abba, baab, baba]
    }

private static String[] findAllCombinations(int n, String[] arrStr) {
        //终止条件
        if (n == 1) {
            return arrStr;
        }
        //储存结果的集合
        TreeSet<Object> strSet = new TreeSet<>();
		//"按住"每个元素
        for (int i = 0; i < arrStr.length; i++) {
            String currentStr = arrStr[i];
            //获取不包含当前元素currentStr的字符串数组
            String[] tempStrArr = getStrArrNotContainStr(arrStr, currentStr);
            //子问题的解
            String[] subproblemResult = findAllCombinations(n - 1, tempStrArr);
            //将子问题的解加上当前元素，构成当前问题的解
            for (int j = 0; j < subproblemResult.length; j++) {
                //当前元素在前
                String s1 = currentStr + subproblemResult[j];
                strSet.add(s1);
                //当前元素在后
                String s2 = subproblemResult[j] + currentStr;
                strSet.add(s2);
            }
        }
        return strSet.toArray(new String[strSet.size()]);
    }

/**
     * 获取arrStr字符串数组中不包含currentStr元素的字符串数组
     * @param arrStr
     * @param currentStr
     * @return
     */
    private static String[] getStrArrNotContainStr(String[] arrStr, String currentStr) {
        ArrayList<String> list = new ArrayList<>();
        for (String s : arrStr) {
            if (!s.equals(currentStr)) {
                list.add(s);
            }
        }
        return list.toArray(new String[list.size()]);
    }
}
```

---

感谢我的好朋友 [玉](https://syfx.github.io/ "玉")，帮助我解决这道题目

算法题--所有排列组合

文章目录

发表评论