题解 | #集合的所有子集(一)#

import java.util.*;

/**
 * NC27 集合的所有子集(一)
 * @author d3y1
 */
public class Solution {
    private ArrayList<ArrayList<Integer>> result = new ArrayList<>();

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param S int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> subsets (int[] S) {
        // return solution1(S);
        return solution11(S);
        // return solution2(S);
    }

    // /**
    //  * 位运算
    //  * @param S
    //  * @return
    //  */
    // private ArrayList<ArrayList<Integer>> solution1(int[] S){
    //     int n = S.length;
    //     if(n == 0){
    //         return new ArrayList<>();
    //     }

    //     Arrays.sort(S);

    //     ArrayList<Integer> list;
    //     StringBuilder binStr;
    //     for(int i=0; i<Math.pow(2,n); i++){
    //         binStr = new StringBuilder(Integer.toBinaryString(i));
    //         while(binStr.length() < n){
    //             binStr.insert(0,'0');
    //         }
    //         list = new ArrayList<>();
    //         for(int j=0; j<n; j++){
    //             if(binStr.charAt(j) == '1'){
    //                 list.add(S[j]);
    //             }
    //         }
    //         result.add(list);
    //     }

    //     return result;
    // }

    /**
     * 位运算
     * @param S
     * @return
     */
    private ArrayList<ArrayList<Integer>> solution11(int[] S){
        int n = S.length;
        if(n == 0){
            return new ArrayList<>();
        }

        Arrays.sort(S);

        ArrayList<Integer> list;
        for(int i=0; i<Math.pow(2,n); i++){
            list = new ArrayList<>();
            for(int j=0; j<n; j++){
                if(((i>>j)&1) == 1){
                    list.add(S[j]);
                }
            }
            result.add(list);
        }

        return result;
    }

    /**
     * 回溯法
     * @param S
     * @return
     */
    private ArrayList<ArrayList<Integer>> solution2(int[] S){
        int n = S.length;
        if(n == 0){
            return new ArrayList<>();
        }

        Arrays.sort(S);

        backtrack(S, 0, new ArrayList<>());

        return result;
    }

    /**
     * 回溯: 递归遍历解空间
     * @param S
     * @param idx
     * @param list
     */
    private void backtrack(int[] S, int idx, ArrayList<Integer> list){
        result.add(list);
        ArrayList<Integer> newList;
        for(int i=idx; i<S.length; i++){
            newList = new ArrayList<>(list);
            newList.add(S[i]);
            backtrack(S, i+1, newList);
        }
    }
}