力扣 中等 78.子集

题目介绍

解法

有两种解法，对于计算[1,2]的子集问题：

解法一：

站在输入的角度思考：每个元素都可以选/不选

代码如下：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ans;
    }

    private void dfs(int[] nums, int i) {
        if (i == nums.length) { // 子集构造完毕
            ans.add(new ArrayList<>(path)); // 复制 path
            return;
        }
        
        // 不选 nums[i]
        dfs(nums, i + 1);
        
        // 选 nums[i]
        path.add(nums[i]);
        dfs(nums, i + 1);
        path.remove(path.size() - 1); // 恢复现场
    }
}

解法二：

站在答案的角度思考
代码如下：

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        dfs(nums, 0);
        return ans;
    }

    private void dfs(int[] nums, int i) {
        ans.add(new ArrayList<>(path)); // 复制 path
        for (int j = i; j < nums.length; j++) { // 枚举选择的数字
            path.add(nums[j]);
            dfs(nums, j + 1);
            path.remove(path.size() - 1); // 恢复现场
        }
    }
}

参考b站灵茶山艾府

原文地址：https://blog.csdn.net/qq_51352130/article/details/142723210

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！