LeetCode刷题【78】子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

 

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

\n

题解

作为算法中常用的一个方法，根据已知推导未知，我们可以这样处理。

要求长度为n的数组的子集一下子不好看出来，那么可以先从简单的情况开始处理，然后处理多加了一个元素的情况，处理后再依次增加处理直到达到了数组原来的长度n的情况。首先假定一个数组【1,2,3,4】

当数组为空的时候只有一种情况[[]]

当数组长度为1的时候[[],[1]]

当数组长度为2的时候[[],[1],[2],[1,2]]

当数组长度为3的时候[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

当数组长度为4的时候[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3],[4],[1,4],[2,4],[1,2,4],[3,4],[1,3,4],[2,3,4],[1,2,3,4]]

这样就很好理解了，每增加一个元素，即表示在原来的结果基础上又增加了额外一个选项，所以，对原来的结果进行遍历，分别加上新加上的选项，而新加的选项是可以不选的，原来的结果也要保留。这样就很明显了，代码：

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (int i = 0; i < nums.length; i++) {
            //根据已知求未知，
            //当nums数组中有i个元素的时候，
            // 其结果集等于原来的i-1个元素的时候的结果集中的元素分别加上i，
            // 把i-1个元素的结果集和i个元素的结果集合并
            List<List<Integer>> tmp = new ArrayList<>();
            for (List<Integer> re : res) {
                List<Integer> reCopy = new ArrayList<>(re);
                reCopy.add(nums[i] );
                tmp.add(reCopy);
            }
            res.addAll(tmp);
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

状态枚举。emm假装自己是二进制运算

import java.util.ArrayList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        res.add(new ArrayList<>());
        numsArr = nums;
        statusArr = new boolean[nums.length];
        while (!finished){
            doPlus();
        }
        return res;
    }

    boolean[] statusArr;
    boolean finished = false;
    int[] numsArr;
    List<List<Integer>> res;
    public void doPlus(){
        boolean step = true;
        for (int i = statusArr.length - 1; i >= 0 && step; i--) {
            if (!statusArr[i]){
                statusArr[i]=true;
                step = false;
            }else{
                statusArr[i]=false;
            }
        }
        List<Integer> tmp = new ArrayList<>();
        for (int i = 0; i < statusArr.length; i++) {
            if (statusArr[i]){
                tmp.add(numsArr[i]);
            }
        }
        res.add(tmp);
        if (tmp.size()==numsArr.length){
            finished = true;
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)