LeetCode第78题：子集（中等）

Tallulah ·

更新时间:2024-11-14

· 904 次阅读

LeetCode第78题：子集（中等）

今日打卡是第22题，之前已经做过

题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
在这里插入图片描述

解题思路：借鉴了77题的思路，又尝试用了一次栈。

class Solution {
    private List<List> ans = new ArrayList();
    private int n;
    public List<List> subsets(int[] nums) {
        this.n = nums.length;
        if(n==0) return ans;
        for(int i=0;i<=n;i++){
            sb(0,n,i,nums,new Stack());
        }
        return ans;
    }
    private void sb(int start,int n,int k,int[] nums,Stack pre){
        if(k==0) ans.add(new ArrayList(pre));
        for(int i=start;i0;i++){
            pre.add(nums[i]);
            sb(i+1,n,k-1,nums,pre);
            pre.pop();
        }
    }
}

在这里插入图片描述

题解做法1：递归

class Solution {
  public List<List> subsets(int[] nums) {
    List<List> output = new ArrayList();
    output.add(new ArrayList());
    for (int num : nums) {
      List<List> newSubsets = new ArrayList();
      for (List curr : output) {
        newSubsets.add(new ArrayList(curr){{add(num);}});
      }
      for (List curr : newSubsets) {
        output.add(curr);
      }
    }
    return output;
  }
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在这里插入图片描述

题解做法2：字典排序

class Solution {
  public List<List> subsets(int[] nums) {
    List<List> output = new ArrayList();
    int n = nums.length;
    for (int i = (int)Math.pow(2, n); i < (int)Math.pow(2, n + 1); ++i) {
      // generate bitmask, from 0..00 to 1..11
      String bitmask = Integer.toBinaryString(i).substring(1);
      // append subset corresponding to that bitmask
      List curr = new ArrayList();
      for (int j = 0; j < n; ++j) {
        if (bitmask.charAt(j) == '1') curr.add(nums[j]);
      }
      output.add(curr);
    }
    return output;
  }
}
作者：LeetCode
链接：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

在这里插入图片描述