Java递归实现字符串的排列和组合

我们在笔试中经常会遇到需要对字符串进行排列或者组合的题目。本篇文章对字符串的排列和组合进行递归版本的实现。

1. 字符串的组合

题目：输入一个字符串，输出该字符串中字符的所有组合。

例子：输入：abc，它的组合有：a、b、c、ab、ac、bc、abc

分析：我们可以将字符串中的每个字符看成二叉树的一个节点，根节点为空，每个节点都会有两种选择：要 和 不要 两种选择。那么我们就可以利用递归实现。

代码实现：

运行结果：

2. 字符串的排列

01

全排列

题目：输入一个字符串，打印出该字符串中字符的所有排列。

举例：输入字符串 abc，则输出由字符 a、b、c 所能排列出来的所有字符串 abc、acb、bac、bca、cab 和 cba。

分析：排列和上面的组合问题思想是一样的：上面的组合问题，每个节点只有 “要” 和 “不要” 两种选择，而排列这里每个节点 i 有 n - i 种选择。

排列问题：所有的排列都是包含该字符串中所有的字符，所以不需要像组合那样利用额外的空间 pre 记录选择的过程。

需要注意的是：i 位置在进行选择的时候，会先和 i + 1 位置交换位置，搞定 i + 1 后面的排列后，会再和 i + 2 ~ n - 1 位置上的每个元素交换一次，所以为了保证都是和 i 位置上的元素进行交换，每次递归一次后，必须要将 i 位置元素再换回原来的位置。

可以直观的理解下：加入现在搞定 i 位置上元素，i 一共有 n - i 种选择，每次 i 位置固定后，i + 1 ~ n - 1 位置上的元素都是同样递归实现。

代码实现：

运行结果：

02

去重全排列

只需要增加一个 hashset，用于保证重复字符不会被再次交换。

运行结果：

-------- END ---------