451，回溯和位运算解子集

Original 山大王wld 数据结构和算法 2022-05-01

收录于合集 #算法图文分析 161个

Whatever tomorrow brings, I'm grateful to see it.

不管明天将带来什么，我都会感激。

问题描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]

输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

回溯解决解决

在前面一道题450，什么叫回溯算法，一看就会，一写就废中提到过子集的问题，这里再来看一下，回溯的模板如下，就是先选择，最后再撤销

 1private void backtrack("原始参数") {
 2    //终止条件(递归必须要有终止条件)
 3    if ("终止条件") {
 4        //一些逻辑操作（可有可无，视情况而定）
 5        return;
 6    }
 7
 8    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
 9        //一些逻辑操作（可有可无，视情况而定）
10
11        //做出选择
12
13        //递归
14        backtrack("新的参数");
15        //一些逻辑操作（可有可无，视情况而定）
16
17        //撤销选择
18    }
19}

这道题也一样，可以把它想象成为一颗n叉树，通过DFS遍历这棵n叉树，他所走过的所有路径都是子集的一部分，看下代码

 1public List<List<Integer>> subsets(int[] nums) {
 2    List<List<Integer>> list = new ArrayList<>();
 3    backtrack(list, new ArrayList<>(), nums, 0);
 4    return list;
 5}
 6
 7private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int start) {
 8    //走过的所有路径都是子集的一部分，所以都要加入到集合中
 9    list.add(new ArrayList<>(tempList));
10    for (int i = start; i < nums.length; i++) {
11        //做出选择
12        tempList.add(nums[i]);
13        //递归
14        backtrack(list, tempList, nums, i + 1);
15        //撤销选择
16        tempList.remove(tempList.size() - 1);
17    }
18}

因为在第450题刚讲过这道题，所以基本上没什么难度，其实这道题还可以使用位运算解决，来看下

位运算解决

数组中的每一个数字都有选和不选两种状态，我们可以用0和1表示，0表示不选，1表示选择。如果数组的长度是n，那么子集的数量就是2^n。比如数组长度是3，就有8种可能，分别是

[0，0，0]

[0，0，1]

[0，1，0]

[0，1，1]

[1，0，0]

[1，0，1]

[1，1，0]

[1，1，1]

这里参照示例画个图来看下

 1public static List<List<Integer>> subsets(int[] nums) {
 2    //子集的长度是2的nums.length次方，这里通过移位计算
 3    int length = 1 << nums.length;
 4    List<List<Integer>> res = new ArrayList<>(length);
 5    //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
 6    for (int i = 0; i < length; i++) {
 7        List<Integer> list = new ArrayList<>();
 8        for (int j = 0; j < nums.length; j++) {
 9            //如果数字i的某一个位置是1，就把数组中对
10            //应的数字添加到集合
11            if (((i >> j) & 1) == 1)
12                list.add(nums[j]);
13        }
14        res.add(list);
15    }
16    return res;
17}

非递归解决

这题还有其他解题思路，比如先加入一个空集让他成为新的子集，然后每遍历一个元素就在原来的子集的后面追加这个值。还以示例来分析下

 1public List<List<Integer>> subsets(int[] nums) {
 2    List<List<Integer>> res = new ArrayList<>(1 << nums.length);
 3    //先添加一个空的集合
 4    res.add(new ArrayList<>());
 5    for (int num : nums) {
 6        //每遍历一个元素就在之前子集中的每个集合追加这个元素，让他变成新的子集
 7        for (int i = 0, j = res.size(); i < j; i++) {
 8            //遍历之前的子集，重新封装成一个新的子集
 9            List<Integer> list = new ArrayList<>(res.get(i));
10            //然后在新的子集后面追加这个元素
11            list.add(num);
12            //把这个新的子集添加到集合中
13            res.add(list);
14        }
15    }
16    return res;
17}

如果非要把它改为递归的也是可以的，仅仅提供了一种思路，有兴趣的也可以看下

 1public List<List<Integer>> subsets(int[] nums) {
 2    List<List<Integer>> res = new ArrayList<>(1 << nums.length);
 3    res.add(new ArrayList<>());
 4    recursion(nums, 0, res);
 5    return res;
 6}
 7
 8public static void recursion(int[] nums, int index, List<List<Integer>> res) {
 9    //数组中的元素都访问完了，直接return
10    if (index >= nums.length)
11        return;
12    int size = res.size();
13    for (int j = 0; j < size; j++) {
14        List<Integer> list = new ArrayList<>(res.get(j));
15        //然后在新的子集后面追加一个值
16        list.add(nums[index]);
17        res.add(list);
18    }
19    //递归下一个元素
20    recursion(nums, index + 1, res);
21}

其他解决方式

在426，什么是递归，通过这篇文章，让你彻底搞懂递归中最后讲到分支污染的时候提到过这样一个问题：生成一个2^n长的数组，数组的值从0到(2^n)-1。我们可以把它想象成为一颗二叉树，每个节点的子树都是一个可选一个不可选

所以我们也可以参照这种方式来写，代码如下

 1public List<List<Integer>> subsets(int[] nums) {
 2    List<List<Integer>> res = new ArrayList<>();
 3    helper(res, nums, new ArrayList<>(), 0);
 4    return res;
 5}
 6
 7private void helper(List<List<Integer>> res, int[] nums, List<Integer> list, int index) {
 8    //终止条件判断
 9    if (index == nums.length) {
10        res.add(new ArrayList<>(list));
11        return;
12    }
13    //每一个节点都有两个分支，一个选一个不选
14    //走不选这个分支
15    helper(res, nums, list, index + 1);
16    //走选择这个分支
17    list.add(nums[index]);
18    helper(res, nums, list, index + 1);
19    //撤销选择
20    list.remove(list.size() - 1);
21}