等　级：新手上路
帖　子：20
专家分：4
注　册：2012-12-5
结帖率：50%
楼主   问题点数：0  回复次数：0         
公司一道面试题，求大神给思路！
输入1234
输出
1
2
3
4
12
13
14
23
24
34
123
124
234
1234
我的思路是，全排列，然后按条件输出，但是空间复杂度和时间复杂度都挺高，求其他思路！

public class Demo {
    public static void main(String[] args){  
            for(int i=1;i<5;i++)
            System.out.println(i);
            for(int i=1;i<5;i++){
            for(int j=i+1;j<5;j++)
            System.out.println(i+""+j);
            }
            for(int i=1;i<5;i++){
            for(int j=i+1;j<5;j++)
            for(int k=j+1;k<5;k++)
            if(i==1&&j==3&&k==4)break;
            else
                System.out.println(i+""+j+""+k);
            }
            System.out.println(1234);
        }  

}

你这样只能满足这个数据，我要是扩展N个数就不适应了

简单，i从0开始循环，j从i+1开始循环，将i*10+j赋值给一个arraylist对象，重写tostring方法输出就可以了

就是子集的可能还要排列……

import java.util.Scanner;

public class 打印所有集合全排列 {
    public static void main(String[] args) {
       
        Scanner sc=new Scanner(System.in);
        char c[]=sc.next().toCharArray();
        char b[];
        for (int i = 1; i <=c.length; i++) {
            b=new char[i];
            组合(c.length,i,c,b);
        }
    }
    public  static void 组合(int n,int k,char c[],char b[]){
        int i;
        if(k==0){
            String s="";
            for (int j = 0; j < b.length; j++) {
                s=s+b[j]+"";
            }
            全排列(0,s.toCharArray());
            return;
        }else{
            for (int j = n-1; j >=0; j--) {
                    b[k-1]=c[j];
                    组合(j,k-1,c,b);
            }
           
        }
       
    }
    public static void 全排列(int k,char c[]){
        if(k>=c.length){
            for (int i = 0; i < c.length; i++) {
                System.out.print(c[i]);
            }
            System.out.println();
            return ;
        }
        for (int i = k; i < c.length; i++) {
            {char temp=c[i];c[i]=c[k];c[k]=temp;}
            全排列( k+1, c);
            {char temp=c[i];c[i]=c[k];c[k]=temp;}
        }
    }
}

看错了…………是组合……

组合数…………

import java.util.Scanner;

public class 打印组合数 {
    public static void main(String[] args) {
       
        Scanner sc=new Scanner(System.in);
        char c[]=sc.next().toCharArray();
        char b[];
        for (int i =1; i <=c.length; i++) {
            b=new char[i];
            组合(c.length,i,c,b);
        }
    }
    public  static void 组合(int n,int k,char c[],char b[]){
        int i;
        if(k==0){
//            String s="";
            for (int j = 0; j < b.length; j++) {
                System.out.print(b[j]);
            }
            System.out.println();
            //全排列(0,s.toCharArray());
            return;
        }else{
            for (int j = n-1; j >=0; j--) {
                    b[k-1]=c[j];
                    组合(j,k-1,c,b);
            }
           
        }
       
    }
//    public static void 全排列(int k,char c[]){
//        if(k>=c.length){
//            for (int i = 0; i < c.length; i++) {
//                System.out.print(c[i]);
//            }
//            System.out.println();
//            return ;
//        }
//        for (int i = k; i < c.length; i++) {
//            {char temp=c[i];c[i]=c[k];c[k]=temp;}
//            全排列( k+1, c);
//            {char temp=c[i];c[i]=c[k];c[k]=temp;}
//        }
//    }
}

abcd//输入的字符串……
d
c
b
a
cd
bd
ad
bc
ac
ab
bcd
acd
abd
abc
abcd