🌕 78. 子集

难度: 🌕

问题描述

---

解法 1 - 二叉树思路

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        // 思路：
        // 无重复数组 & 无重复选取组合
        int len = nums.length;
        LinkedList<Integer> path = new LinkedList<>();
        mySol(nums, len, 0, path);
        return res;
    }

    private void mySol(int[] nums, int len, int index, LinkedList<Integer> path) {
        // 递归终止条件
        if(index == len) {
            res.add(new LinkedList<>(path));
            return;
        }
        // 类似二叉树，当前 index 有2种选择
        mySol(nums, len, index + 1, path);
        path.addLast(nums[index]);
        mySol(nums, len, index + 1, path);
        path.removeLast();
    }
}

---

输出 1

---

解法 2 - 通用

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        // 思路：
        // 无重复数组 & 无重复选取组合
        int len = nums.length;
        LinkedList<Integer> path = new LinkedList<>();
        mySol(nums, len, 0, path);
        return res;
    }

    private void mySol(int[] nums, int len, int index, LinkedList<Integer> path) {
        // 递归终止条件
        if(index > len) {
            return;
        }
        res.add(new LinkedList<>(path));
        for(int i = index; i < len; i ++) {
            path.addLast(nums[i]);
            mySol(nums, len, i + 1, path);
            path.removeLast();
        }
    }
}

---

输出