【Leetcode 热题 100】78. 子集

问题背景

给你一个整数数组 $nums$，数组中的元素 互不相同 。返回该数组所有可能的 子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

数据约束

• $1\le nums.length\le 10$
• $-10\le nums[i]\le 10$
• $nums$中的所有元素 互不相同

解题过程

子集问题同样可以考虑每个位置上选或不选，或者每一次选哪个元素。

具体实现

选或不选

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, nums, path, res);
        return res;
    }

    private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> res) {
        if(i == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        dfs(i + 1, nums, path, res);
        path.add(nums[i]);
        dfs(i + 1, nums, path, res);
        path.remove(path.size() - 1);
    }
}

选哪一个

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, nums, path, res);
        return res;
    }

    private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> res) {
        res.add(new ArrayList<>(path));
        // 注意 j 要从 i 开始枚举，不要走回头路
        for(int j = i; j < nums.length; j++) {
            path.add(nums[j]);
            dfs(j + 1, nums, path, res);
            path.remove(path.size() - 1);
        }
    }
}