LeetCode 78. 子集

78. 子集

解题思路

递归 + 回溯
每一个节点都会有两种选择，选或者不选

参考代码

class Solution {
    private List<List<Integer>> res = new ArrayList<>();
    private List<Integer> tmp = new ArrayList<>();
    private int path_len = 0;

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

    private void dfs(int[] nums) {
        if(path_len == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        // 选当前节点
        tmp.add(nums[path_len]);
        path_len ++;
        dfs(nums);
        path_len --;
        tmp.remove(tmp.size() - 1);

        // 不选当前节点
        path_len ++;
        dfs(nums);
        path_len --;
    }
}