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

import java.util.*;


public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    int n;
    ArrayList<Integer> path = new ArrayList<>();
    boolean[] used = new boolean[n];
    public ArrayList<ArrayList<Integer>> subsets (int[] nums) {
        Arrays.sort(nums);
        n = nums.length;
        for (int i = 0; i <= n; i++) {
            dfs(0, i, nums);
        }
        res.sort(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                ArrayList<Integer> o11 = (ArrayList<Integer>) o1;
                ArrayList<Integer> o12 = (ArrayList<Integer>) o2;
                int i = 0;
                int j = 0;
                while (i < o11.size() || j < o12.size()) {
                    int x = Integer.MIN_VALUE;
                    int y = Integer.MIN_VALUE;
                    if (i == o11.size()) {
                        y = o12.get(j);
                        i++;
                    } else if (j == o12.size()) {
                        x = o11.get(i);
                        j++;
                    } else {
                        x = o11.get(i);
                        y = o12.get(j);
                        i++;
                        j++;
                    }
                    if (x > y) return 1;
                    if (x < y) return -1;
                }
                return 0;
            }
        });
        return res;
    }

    void dfs(int start, int k, int[] nums) {
        if (k == 0) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < n; i++) {
            if (i > start && nums[i - 1] == nums[i]) continue;
            path.add(nums[i]);
            dfs(i + 1, k - 1, nums);
            path.remove(path.size() - 1);
        }
    }
}

我用的是经典模板，更好理解，这里稍微麻烦的是需要传入一个comparator比较器,因为牛客需要按字典序输出。

题的执行过程:

我需要获得长度为0到n的子集序列，先从0开始，如果此时所需寻找的子集长度为0，添加到结果集，

然后寻找长度为1的子集序列，start下标在每次寻找时都要加一，保证子集不会回头去找。

去重的话，使用i>start和nums[i] == nums[i-1] continue 来保证不会有重复的。

举个例子: 1 2 2

先找子集个数为0的，此时需要的子集个数为0，return。

再找子集个数为1的，传入start=0， k = 1, 表示从第一个开始取数，此时需要的子集个数为1，找到之后，加入path，k-1；

此时k=0，将它加入到结果集。

循环，从 下标一开始，如果与前一个相同，则会重复，所以continue，接着刚才的操作。

理解起来很难，加油。