所有子集

酒楼

发布于 2024-01-06 09:38:35

960

发布于 2024-01-06 09:38:35

文章被收录于专栏：酒楼酒楼

所有子集

给定一个整数数组 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 中的所有元素 互不相同

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;
        //利用mask做掩码000，001，010，011，100，101，110，111
        for(int mask = 0;mask<(1<<n); ++mask){
            t.clear();
            for(int i=0;i<n;++i){
                //当mask=3时，011
                //i = 0 ; 1<<i = 1 ; mask&1 = 1; t.add(1)
                //i = 1 ; 1<<i = 2 ; mask&0 = 1; t.add(2)
                //i = 2 ; 1<<i = 4 ; mask&4 = 0;
                if((mask &(1<<i)) !=0){
                    t.add(nums[i]);
                }
            }
        }
        ans.add(new ArrayList<Integer>(t));
    }
    return ans;
}

2.递归

class Solution{
    List<Integer> t= new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
    public List<List<Integer>> subsets(int[] nums){
        dfs(0,nums);
        return ans;
    }
    
    public void dfs(int cur,int[] nums){
        if(cur == nums.length){
            ans.add(new ArrayList<Integer>(t));
            return;
        }
        
        //list添加当前节点，再递归剩下的
        t.add(nums[cur]);
        dfs(cur + 1,nums);
        //list移除当前节点，再递归剩下的
        t.remove(t.size() -1);
        dfs(cur + 1,nums);
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-01-05，如有侵权请联系 cloudcommunity@tencent.com 删除

integer