获取字符组所有排列字符串的算法

刚看了论坛上有个很有意思的递归算法题，忍不住自己也动手来写写看。

比如给定一个字符串 “123”， 求出用1,2,3能排列出来的所有组合。

	/**
	 * 1.对于每个需要需要获取排列集合的字符串，先获取最左边第一个字符c，然后获取右边字符串所有排列的集合
	 * 2.然后对每一个排列集合中的字符串，进行c的插入，从左到右，一共可以插入（长度+1）次，获得（长度+1）新字符串
	 * 3.递归调用的最底层，input字符串只有一个字符的时候，返回只有这个字符的排列集合
	 * @param input
	 * @return
	 */
	public static List<String> getStringSorts(String input){
		List<String> allSortedList=new ArrayList<String>();
		char leftChar=input.charAt(0);
		if(input.length()>1){
			String rightString=input.substring(1,input.length());
			List<String> rightStringSortedList=getStringSorts(rightString);
			for(String rightStringTmp:rightStringSortedList){
				for(int i=0;i<rightStringTmp.length()+1;i++){
					allSortedList.add(new StringBuffer(rightStringTmp).insert(i, leftChar).toString());
				}
			}
		}else{
			allSortedList.add(String.valueOf(leftChar));
		}
		return allSortedList;
	}

写代码验证：将结果放到一个Set里面，然后再比较List和Set的长度

		List<String> list=getStringSorts("12345");
		Set<String> validateSet=new HashSet<String>();
		for(String tmp:list){
			System.out.println(tmp);
			validateSet.add(tmp);
		}
		System.out.println("total: "+list.size());
		System.out.println("validate: "+validateSet.size());