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

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

题目

Subsets : https://leetcode.com/problems/subsets/
如果S=[1,2,3], 给出所有子集。
如：
[↵ [3],↵ [1],↵ [2],↵ [1,2,3],↵ [1,3],↵ [2,3],↵ [1,2],↵ []↵ ]

解题思路

1、回溯法动态规划。

回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

2、位运算 迭代法实现 子集枚举
3、递归法实现子集枚举
4、常规思路，非递归

解题思路一: 位运算 迭代法实现 子集枚举

思路与算法

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

假设原序列中元素的总数为 n。
原序列中的每个数字 a(i) 的状态可能有两种，即「在子集中」和「不在子集中」。
我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 a(i) 是否在子集中。

例如，n = 3n=3 ，a = { 5, 2, 9 } 时：

0/1 序列对应的二进制数正好从 00 到 2^n - 1。我们可以枚举 mask ∈ [0, 2^n−1]，mask 的二进制表示是一个 0/1 序列，我们可以按照这个 0/1 序列在原集合当中取数。
当我们枚举完所有 2^n个 mask，我们也就能构造出所有的子集。

示例图

代码实现

    public static  List<List<Integer>> method4(Integer[] nums) {
        // 子集列表
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();

        int len = nums.length;

        // 获得所有子集数. 1<<nums.length 等价于 2^nums.length,对于n个数字的数组，共2^n个子集
        //子集的长度是2的nums.length次方，这里通过移位计算
        int soo = 1 << len; // or  (int) Math.pow(2, len);
        System.out.println("子集数量：" + soo);

        //遍历从0到length中间的所有数字，根据数字中1的位置来找子集
        for (int mask = 0; mask < soo; ++mask) {
            temp.clear();
            for (int j = 0; j < len; ++j) {
                // 查看对应的二进制
//                String binaryMask = Integer.toBinaryString(mask);
//                String binarySpo = Integer.toBinaryString(1 << j);
                // ((mask >> j) & 1) 指 如果数字 mask 的某一个位置是1，就把数组中对应的数字添加到集合
                // 此处两种写法均可以：` (mask & (1 << j)) != 0 ` 或者 ` ((mask >> j) & 1) == 1 `
                if (((mask >> j) & 1) == 1) {
                    temp.add(nums[j]);
                }
            }

            // 添加一个计算出的子集
            res.add(new ArrayList<>(temp));
        }

        return res;
    }

输出:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

复杂度分析

• 时间复杂度：O(n * 2^n)。一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
• 空间复杂度：O(n)。即构造子集使用的临时数组 t 的空间代价。

解题思路二: 递归法实现子集枚举

代码实现

public static List<List<Integer>> method2(Integer[] nums) {
        // 子集列表
        List<List<Integer>> res = new ArrayList<>();

        Arrays.sort(nums);
        dfs(res, nums, new ArrayList<>(), 0);

        return res;
}

/**
 *
 * @param res 输出的结果集合
 * @param nums 原始数组
 * @param tmp   临时对象
 * @param cur 表示当前位置
 */
private static void dfs(List<List<Integer>> res, Integer[] nums, ArrayList<Integer> tmp, int cur) {
        if (nums.length == cur) {
            res.add(new ArrayList<>(tmp));
        } else {
            tmp.add(nums[cur]);

            dfs(res, nums, tmp, cur + 1);
            tmp.remove(tmp.size() - 1);
            dfs(res, nums, tmp, cur + 1);
        }
}

输出:

[[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

复杂度分析

• 时间复杂度：O(n * 2 ^ n)。一共 2^n个状态，每种状态需要 O(n)的时间来构造子集。
• 空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为 O(n)。

解题思路三: 常规思路，非递归

思路与算法

对于例子[1,2,3]来说，最开始是空集，那么我们现在要处理1，就在空集上加1，为[1]。
现在我们有两个自己[]和[1]，下面我们来处理2，我们在之前的子集基础上，每个都加个2，可以分别得到[2]，[1, 2]。那么现在所有的子集合为[], [1], [2], [1, 2]。

同理处理3的情况可得[3], [1, 3], [2, 3], [1, 2, 3], 再加上之前的子集就是所有的子集合了。

代码实现

public static List<List<Integer>> method1(Integer[] nums) {
        // 子集列表
        List<List<Integer>> res = new ArrayList<>();

        // 空集
        res.add(new ArrayList<>());

        if(nums==null||nums.length==0){
            return res;
        }

        // 非空集
        for(int i=0; i< nums.length; i++){
            // 目前已经存在的子集数量
            int size = res.size();

            for(int j=0; j<size; j++){
                // 取得该具体的子集
                List<Integer> cur=new ArrayList<>(res.get(j));
                // 子集中追加 i
                cur.add(nums[i]);

                // 追加后的列表作为新子集
                res.add(new ArrayList<>(cur));
            }
        }

        return res;
}

输出

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

解题思路四： 回溯法动态规划

代码实现

public static  List<List<Integer>> method3(Integer[] nums) {
        // 子集列表
        List<List<Integer>> res = new ArrayList<>();

        backtrack(res, nums, new ArrayList<>(), 0);

        return res;
}

private static void backtrack(List<List<Integer>> res, Integer[] nums, ArrayList<Integer> tmp, int start) {
        //走过的所有路径都是子集的一部分，所以都要加入到集合中
        res.add(new ArrayList<>(tmp));

        for(int i = start; i < nums.length; i++){
            //做出选择
            tmp.add(nums[i]);
            //递归
            backtrack(res, nums, tmp, i + 1);
            //撤销选择
            tmp.remove(tmp.size() - 1);
        }
}

输出：

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

~ end