输出字符串的所有组合的java实现

待我称王封你为后i 2021-09-15 00:40 308阅读 0赞

问题描述：假设字符串中的所有字符不重复，如何输出字符串的所有组合，例如，输入字符串为“abc”，则输出a、b、c、ab、ac、bc、abc，共7种组合。

根据题意，如果字符串中有n个字符，根据排列组合的性质，此时一共需要输出2^n-1种组合。

> 最容易想到的方式是递归，遍历字符串，每个字符串只能取或不取。若取该字符，就把它放到结果字符串中，遍历完毕后，输出结果字符串。

程序代码为：

>     public class CombineRecursiveImpl {
>     	public static void main(String[] args) {
>     		char[] c=s.toCharArray();
>     		StringBuffer sb=new StringBuffer("");
>     		System.out.println(sb);
>     		int len=c.length;
>     		for(int i=1;i<=len;i++){
>     			Solution3.combineRecursive(c, 0, i, sb); 
>     		}
>     		
>     	}
>     
>     }
>     
>     class Solution3{
>     	public static void combineRecursive(char[] c,int begin,int len,StringBuffer sb){
>     		if(len==0){
>     			System.out.print(sb+" ...");
>     			return;
>     		}
>     		if(begin==c.length){
>     			return;
>     		}
>     		sb.append(c[begin]);
>     		System.out.print(sb+",");
>     		combineRecursive(c, begin+1, len-1, sb);
>     		sb.deleteCharAt(sb.length()-1);
>     		System.out.print(sb+",");
>     		combineRecursive(c, begin+1, len, sb);
>     	}
>     }
> 
> 运行结果为：

> >  a  b  c  ab  ac  bc abc

采用递归法求解，当n的值不是很大时，不存在效率低下的问题，但当n比较大时，效率会变得很差，因为栈调用次数约为2^n，为了提高效率，考虑本题的特性，可以构造一个长度为n的01字符串（或二进制数）表示输出结果中是否包含某个字符，例如，“001”表示输出结果中不含字符a、b，只含c，即输出结果为c，而“101”，表示输出结果为ac。原题就是要求输出“001”到“111”这2^n-1个组合对应的字符串。

程序代码如下：

>     public class CombineRecursiveImpl {
>     
>     	public static void main(String[] args) {
>     		String s="abc";
>     		char[] c=s.toCharArray();
>     		Solution4.Combine(c);
>     	}
>     
>     }
>     
>     class Solution4{
>     	public static void Combine(char[] c){
>     		if(c==null){
>     			return;
>     		}
>     		int len=c.length;
>     		boolean[] used=new boolean[len];
>     		char cache[]=new char[len];
>     		int result=len;
>     		while(true){
>     			int index=0;
>     			while(used[index]){
>     				used[index]=false;
>     				++result;
>     				if(++index==len){
>     					return;
>     				}
>     			}
>     			used[index]=true;
>     			cache[--result]=c[index];
>     			System.out.print(new String(cache).substring(result)+" ");
>     		}
>     	}
>     }
> 
> > 运行结果为：
> 
> > >  a  b  c  ab  ac  bc abc