题目描述
输入一串字符串，输出该字符串所有的排列，并且无重复。
例如，输入：“abc”，输出：abc、acb、bac、bca、cab、cba
解决思路
正常思维，先固定一字母，求之后字母的全排列，该问题可划分为更小的子问题，直到所求子问题规模为0，输出结果。显然，使用递归的思路求解，下图为递归的过程：
image.png
递归具有两个基本特征：递归终止条件与递归式
- 递归终止条件：当所求全排列问题规模为0，即字符串长度为0
- 递归式：将所有全排列字符串的第一个字符依次与后面字符交换，然后递归进入下一层，递归返回时，还原交换
代码实现
package lanqiao.practise;
import java.util.Scanner;
public class Permutation {
public static void main(String[] args) {
// TODO Auto-generated method stub
//input a string ,output the permutation using recursive
Scanner s = new Scanner(System.in);
String string = s.nextLine();
char[] a = string.toCharArray();
permutation(a,a.length);
}
public static void permutation(char[] a,int n) {
if(a.length == 0)
return ;
else {
permutate(a,0,n);
}
}
public static void permutate(char[] a,int k,int n) {
if(k==n) {
System.out.println(a);
return ;
}
for(int i=k;i<n;i++) {
//to prevent the repeated string, we could add a judgement
if(i!=k&&a[i] == a[k])
continue;
swap(a,k,i);
permutate(a,k+1,n);
swap(a,k,i);
}
}
public static void swap(char[] a,int i,int j) {
char temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
