一个算法命题：给定字符串S[0…N-1]，设计算法，枚举S的全排列。如：123，全排列就是：123,132,213,231,312,321
java代码：递归实现（考虑有重复的字符）
以字符串1234为例：
1 – 234
2 – 134
3 – 214
4 – 231
如何保证不遗漏： 每次递归前，保证1234的顺序不变。
1 package stringtest; 2 import java.util.ArrayList; 3 import java.util.Collections; 4 5 /**题目描述 6 输入一个字符串,按字典序打印出该字符串中字符的所有排列。 7 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 8 输入描述: 9 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。 10 * 11 * 12 * @author Administrator 13 * 14 */ 15 public class FullArray { 16 17 public static void main(String[] args) { 18 FullArray fa = new FullArray(); 19 String str = "abc"; 20 ArrayList<String> arrayList = fa.Permutation(str); 21 for (String string : arrayList) { 22 System.out.println(string); 23 } 24 } 25 26 /** 27 * 思路：利用递归的思想。来实现 28 * 先让a第一位：剩余bcd做全排列 29 * 先让b第一位：剩余acd做全排列 30 * 先让c第一位：剩余abc做全排列 31 * 先让d第一位：剩余abc做全排列 32 * 33 * @param str 34 * @return 35 */ 36 ArrayList<String> list = new ArrayList<>(); 37 public ArrayList<String> Permutation(String str) { 38 char[] array = str.toCharArray(); 39 permutaionTest(array,0,str.length()-1); 40 Collections.sort(list); 41 return list; 42 } 43 44 public void permutaionTest(char[] array,int start,int end){ 45 //递归退出条件 46 if(array.length<1){ 47 return; 48 } 49 //如果start和end不相等，说明完成一次排序 50 if(start==end){ 51 String val = new String(array); 52 //这里也是判断元素重复情况(方式一) 53 if (!list.contains(val)) 54 list.add(val); 55 }else{ 56 //回溯法，每次固定一个元素在最前面，后面元素进行全排列 57 for (int i = start; i <= end; i++) { 58 59 //考虑有重复元素的情况(方式二) 60 boolean flag = true; 61 for (int j = start; j < i; j++) { 62 if(array[j] == array[i]){//这里吧i换成end也行 63 flag = false; 64 } 65 } 66 67 //有重复元素就跳过大循环，下一个比较 68 if(flag){ 69 swap(array,start,i); 70 permutaionTest(array,start+1,end); 71 swap(array,i,start); 72 } 73 } 74 } 75 } 76 77 private void swap(char[] array, int start, int i) { 78 if(start!=i){ 79 char tmp = array[start]; 80 array[start] = array[i]; 81 array[i] = tmp; 82 } 83 } 84 }