78. Subsets

题目分析

找一个集合的所有子集 + 回溯法

代码

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null) {
            return res;
        }
        // 注意空集 [] 是有子集的，空集的唯一子集就是自身
        if(nums.length == 0) {
            res.add(new ArrayList<Integer>());
            return res;
        }
        helper(new ArrayList<Integer>(), nums, 0, res);
        return res;
    }
    public void helper(ArrayList<Integer> subset, int[] nums, int startIndex, List<List<Integer>> res) {
        // 注意这里 new 了一个新的 ArrayList 来实现深拷贝
        // 这里也不用判断是不是找到了解，直接添加解到结果集
        res.add(new ArrayList<Integer>(subset));
        // 枚举所有可能的路径
        for(int i = startIndex; i < nums.length; i++) {
            // 也不用判断是不是满足约束条件，题目要求枚举所有可能的子集
            subset.add(nums[i]);
            // 扩展下一个位置
            helper(subset, nums, i + 1, res);
            // 回溯，清理所占用的状态
            subset.remove(subset.size() - 1);
        }
        
    }
}