题目描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

不能包含重复子集

样例

intput: nums = [1,2,3]
oupput：[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
即输出包括空集在内的所有子集
题目不要求按照特定顺序输出，只要结果包含所有子集即可
题目要求结果不能包含重复子集，如[1,3] 和[3,1]是一个重复子集

算法1

dfs + recursion + backtracking

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

    dfs(nums, 0, new ArrayList<Integer>());
    return res;
}

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

算法理解：1、for loop枚举的是什么信息 2、start控制的是什么

–for loop枚举的是位置，即选择nums中哪个位置的数
–start控制选择的顺序，只能往下一个位置选，不能回头！避免重复

dfs recursion的过程可以模拟成tree上的preorder travel
path 即 preorder travel的当前路径

                                         []
                                       []
                                    /   |  \
                               [1] 1 [2]2   3[3]
                                 /  \   |
                           [1,2]2    3  3[2,3]
                               /   [1,3]
                      [1,2,3] 3

按照preorder的输出顺序，算法输出结果是:[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

时间复杂度

O(2^n) 2的n次方

空间复杂度

不考虑inout和output，只考虑extra space
算法只在dfs recursion占用了stack空间
extra space: O(n) n是nums长度