Day42 子集

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

https://leetcode-cn.com/problems/subsets/

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

示例1：

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

示例2：

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

提示：

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

Java解法

思路：

• 所有子集，类似一个排列组合的问题，尝试循环处理，但是漏掉了两两配合
• 参考官方解使用回溯处理
• 每个位置只有添加不添加两种状态，因此添加，复位不添加处理

package sj.shimmer.algorithm.m2;

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

/**
 * Created by SJ on 2021/3/7.
 */

class D42 {
    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }
    static List<Integer> t = new ArrayList<Integer>();
    static List<List<Integer>> result = new ArrayList<List<Integer>>();

    public static List<List<Integer>> subsets(int[] nums) {
        backTract(0, nums);
        return result;
    }


    public static void  backTract(int index,int[] nums) {
        if (index == nums.length) {
            result.add(new ArrayList<Integer>(t));
            return;
        }
        t.add(nums[index]);
        backTract(index + 1, nums);
        t.remove(t.size() - 1);
        backTract(index + 1, nums);
    }
}

image

官方解

https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/

1. 迭代法实现子集枚举

   通过存在不存在转换为 二进制来表示对应集合的二机制数

   class Solution {
       List<Integer> t = new ArrayList<Integer>();
       List<List<Integer>> ans = new ArrayList<List<Integer>>();
   
       public List<List<Integer>> subsets(int[] nums) {
           int n = nums.length;
           for (int mask = 0; mask < (1 << n); ++mask) {
               t.clear();
               for (int i = 0; i < n; ++i) {
                   if ((mask & (1 << i)) != 0) {
                       t.add(nums[i]);
                   }
               }
               ans.add(new ArrayList<Integer>(t));
           }
           return ans;
       }
   }
   

   • 时间复杂度：O(n×2^n)
   • 空间复杂度：O(n)

2. 递归法实现子集枚举

   参考处理

   • 时间复杂度：O(n×2^n)
   • 空间复杂度：O(n)