子集类型

# 78. 子集 (opens new window)

方法一：选哪个？

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ret;
    }
    void dfs(int i){
        ret.add(new ArrayList<>(path));
        if(i==nums.length){
            return ;
        }
        for(int j=i;j<nums.length;j++){
            path.add(nums[j]);
            dfs(j+1);
            path.remove(path.size()-1);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：选或不选

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        dfs(0);
        return ret;
    }
    void dfs(int i){
        if(i==nums.length){
            ret.add(new ArrayList<>(path));
            return ;
        }
        // 选
        path.add(nums[i]);
        dfs(i+1);
        path.remove(path.size()-1);
        dfs(i+1);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 90. 子集 II (opens new window)

class Solution {
    List<List<Integer>> ret = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    int[] nums;
    boolean[] vis;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        this.nums = nums;
        this.vis = new boolean[nums.length];
        Arrays.sort(nums);
        dfs(0);
        return ret;
    }
    void dfs(int i){
        ret.add(new ArrayList<>(path));
        if(i==nums.length){
            return ;
        }
        for(int j=i;j<nums.length;j++){
            // !vis[j-1] 是因为 先执行dfs，出栈时已经置为false，第二个2就不执行了
            if(j>0 && nums[j]==nums[j-1] && !vis[j-1]){
                continue;
            }
            path.add(nums[j]);
            vis[j] = true;
            dfs(j+1);
            path.remove(path.size()-1);
            vis[j] = false;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

# 491. 递增子序列 (opens new window)

← 组合类型排列类型→