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

import java.util.*;

public class Solution {
    
    public class ComparaInteger implements Comparator<Integer> {
        @Override
        public int compare(Integer num1, Integer num2) {
            return num1 - num2;
        }
    }
    
    public class ComparaArrayList implements Comparator<ArrayList<Integer>> {
        @Override
        public int compare(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
            int len1 = arr1.size();
            int len2 = arr2.size();
            int p1 = 0;
            int p2 = 0;
            while (p1 < len1 && p2 < len2) {
                if (arr1.get(p1) < arr2.get(p2)) {
                    return -1;
                }
                else if (arr1.get(p1) > arr2.get(p2)) {
                    return 1;
                }
                else {
                    p1++;
                    p2++;
                }
            }
            if (len1 < len2) {
                return -1;
            }
            else if (len1 > len2) {
                return 1;
            }
            else {
                return 0;
            }
        }
    }
    
    ArrayList<ArrayList<Integer>> arrayList = new ArrayList<>();
    int len = 0;
    
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        
        len = S.length; // 获取数组 S 的长度
        
        // 一些特殊情况的处理
        if (0 == len) {
            return arrayList;
        }
        
        ArrayList<Integer> tmpArrayList = new ArrayList<>();
        process(S, 0, tmpArrayList);
        // 不好意思，看错了，题目没有要求最终的结果集需要排序
        // 在返回最终的结果集之前，需要对结果集进行排序
        // arrayList.sort(new ComparaArrayList());
        return arrayList;
    }
    
    public void process(int[] S, int start, ArrayList<Integer> tmpArrayList) {
        
        // 什么都不要想，一上来就直接将当前已经得到的子集，添加到结果集当中去
        // 复制一份 tmpArrayList
        ArrayList<Integer> addArrayList = new ArrayList<>();
        addArrayList.addAll(tmpArrayList);
        // 对 addArrayList 进行排序
        addArrayList.sort(new ComparaInteger());
        // 将子集添加到结果集当中去
        arrayList.add(addArrayList);
        
        if (start >= len) { // 此时 S 中没有可供我们选择的数字了
            return;
        }
        
        for (int i = start; i < len; i++) {
            tmpArrayList.add(S[i]); // 从数组 S 中获取一个数字，添加到当前的子集中去
            process(S, i + 1, tmpArrayList);
            tmpArrayList.remove(tmpArrayList.size() - 1); // 回溯
        }
        return;
    }
}