求字元串的子集

之前參加了一次面試的筆試考試，裡面有一道：求字元串的子集，例如求1234的子串，有1，2，3，4，12，13，14，23，24，34，123，124，134，234，1234..，當時居然沒想出怎麼做，後面進入二面的時候，面試官問了筆試這道題現在覺得應該怎麼做，很遺憾的是我筆試之後沒有認真的思考，吸取這次教訓，參考了網上的一些思路，利用遞歸是最簡單的方法求出一個字元串所有的子集。

集合中的所有元素對于每一個子集來說，都有兩種可能性：在子集中或是不在子集中。

各個元素的這兩種可能性組合起來，組成了一個集合的所有子集。每一個集合都有2^n個子集。真子集則為：(2^n)-1

我們把元素這種在或不在子集中狀态，放置在boolean數組中。

/**
 * 求1234的子串，例如：1，2，3，4，12，13，14，23，24，34，123，124，134，234，1234
 * 
 * 集合中的所有元素對于每一個子集來說，都有兩種可能性：在子集中或是不在子集中。
 * 各個元素的這兩種可能性組合起來，組成了一個集合的所有子集。每一個集合都有2^n個子集。
 * 
 * 我們把元素這種在或不在子集中狀态，放置在boolean數組中。
 * @author c
 *
 */
public class Test {


    private static void get_Subset(String str, int start, int end, boolean[] b) {
        // TODO Auto-generated method stub
        if(start==end){//當start==end時，即集合中的所有元素都已經在或者不在該子集中，輸出該子集後，return跳出該層遞歸。 
            int i = ;
            for(;i<end;i++){
                if(b[i]){
                    System.out.print(str.charAt(i));
                }
            }
            System.out.print(" ");
            return ;
        }else{
            b[start] = false;//代表數組中索引為start的元素不在該子集中
            get_Subset(str, start+, end, b);//而後進入遞歸，元素索引向後加一，同樣索引為start+1的元素也有在或者不在該子集中兩種可能性
            b[start] = true;
            get_Subset(str, start+, end, b);
        }
    }

    public static void main(String[] args) {
        String str = "1234";
        //我們把元素這種在或不在子集中狀态，放置在boolean數組中。
        boolean []b = new boolean[str.length()];
        get_Subset(str,,str.length(),b);
    }

}
           

結果如下：