78. Subsets

,

Backtracking

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
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        // 子集与全排列的区别在于子集在选择时部分元素可以不选，而全排列在选择时每个元素最终都必须被选择
        List<List<Integer>> resultList = new ArrayList<>();
        List<Integer> numList = new ArrayList<>(nums.length);
        dfs(resultList, numList, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, List<Integer> numList, int[] nums, int index) {
        if (index == nums.length) {
            // 已无元素可再被选择，此时收集
            resultList.add(new ArrayList<>(numList));
            return;
        }

        // not choose
        dfs(resultList, numList, nums, index + 1);

        // choose
        numList.add(nums[index]);
        dfs(resultList, numList, nums, index + 1);
        numList.remove(numList.size() - 1);
    }
}

以上通过对每个元素执行选与不选实现。

Backtracking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        Deque<Integer> subList = new LinkedList<>();
        dfs(resultList, subList, nums, 0);
        return resultList;
    }

    private void dfs(List<List<Integer>> resultList, Deque<Integer> subList, int[] nums, int startIndex) {
        resultList.add(new ArrayList<>(subList));

        for (int i = startIndex; i < nums.length; i++) {
            subList.add(nums[i]);
            dfs(resultList, subList, nums, i + 1);
            subList.removeLast();
        }
    }
}

以上通过枚举不同起点实现，通过每次推进搜索的起点保证不会生成重复的子集。

Bit

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int count = 1 << nums.length;
        List<List<Integer>> resultList = new ArrayList<>(count);
        for (int mask = 0; mask < count; mask++) {
            List<Integer> collection = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                if (((mask >> i) & 1) != 0) {
                    collection.add(nums[i]);
                }               
            }
            resultList.add(collection);
        }
        return resultList;
    }
}

References

78. Subsets
剑指 Offer II 079. 所有子集