leet code78. 子集 && 90. 子集 II

78. 子集 90. 子集 II

78.题目描述

给你一个整数数组 nums ，数组中的元素 互不相同 。

返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。

你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]

输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：
● 1 <= nums.length <= 10
● -10 <= nums[i] <= 10
● nums 中的所有元素 互不相同

90.题目描述

给你一个整数数组 nums ，

其中可能包含重复元素，

请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。

返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

提示：
● 1 <= nums.length <= 10
● -10 <= nums[i] <= 10

题目解析

• 两道题目有异曲同工之妙
• 第 90 题的难点在于如何去重

• 代码上的区别在于多一个去重判断即可

78.code

class Solution {

    private List<List<Integer>> ans;

    private int[] nums;

    public List<List<Integer>> subsets(int[] nums) {
        ans = new ArrayList<>();
        this.nums = nums;

        List<Integer> local = new ArrayList<>();
        dfs(local, 0);

        return ans;
    }

    private void dfs(List<Integer> local, int i) {
        if(i == nums.length) {
            ans.add(new ArrayList<>(local));
            return;
        }

        local.add(nums[i]);
        dfs(local, i + 1);
        local.remove(local.size() - 1);

        dfs(local, i + 1);
    }

}

90.code

class Solution {

    private List<List<Integer>> ans;

    private int[] nums;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans = new ArrayList<>();
        this.nums = nums;

        List<Integer> local = new ArrayList<>();
        Arrays.sort(nums);
        // false 代表没有选择上一个数字
        dfs(local, 0, false);

        return ans;
    }

    private void dfs(List<Integer> local, int i, boolean flag) {
        if(i == nums.length) {
            ans.add(new ArrayList<>(local));
            return;
        }

        // 不选择当前数字
        dfs(local, i + 1, false);

        // 如果当前数字和前一个数字相同，且前一个数字没有被选择，直接跳过
        if(!flag && i > 0 && nums[i] == nums[i - 1]) {
            return;
        }

        local.add(nums[i]);
        dfs(local, i + 1, true);
        local.remove(local.size() - 1);
    }

}