长大后想做什么？做回小孩！

0%

LeetCode——子集

发表于 分类于 Valine：
本文字数： 164

NO.78 子集 中等

8jYbHH.png

思路一：回溯法 “组合”、”排列”、”子集”这些字眼很容易想到回溯。

依然是走重复的路即可。不过求所有子集的问题，不仅仅是保存叶子节点，而是每个节点都需要保存。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
List<List<Integer>> res=new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
    if (nums==null||nums.length<0)return res;
    dfs(nums,0,new LinkedList<Integer>());
    return res;
}

private void dfs(int[] nums, int index, LinkedList<Integer> track) {
    res.add(new ArrayList<>(track));
    for (int i = index; i < nums.length; i++) {
        track.add(nums[i]);
        dfs(nums,i+1,track);
        track.removeLast();
    }
}

时间复杂度：O(n*2^n) n数组元素个数。生成每个子集最多需要n的时间，共有2^n个子集。

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github