子集

来源Leetcode第78题子集

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

说明：解集不能包含重复的子集。
示例:

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

---

回溯

同第77题组合，修改第77题的代码，从1 组合到n即可。
注意要加上空集。

代码如下:

List<List<Integer>> res = new ArrayList<>();
public void backtrack( int first,ArrayList<Integer> curr,int k,int []nums){
    if(curr.size() == k){
        res.add(new ArrayList<>(curr));
        return;
    }

    for(int i = first;i <= nums.length - k + curr.size() + 1 ; ++i) {
        curr.add(nums[i - 1]);
        backtrack(i + 1, curr,k,nums);
        curr.remove(curr.size() - 1);
    }
}

public List<List<Integer>> combine(int k,int[] nums) {
    backtrack(1,new ArrayList<Integer>(),k,nums);
    return res;
}

public List<List<Integer>> subsets(int[] nums) {
    if(nums.length == 0)
        return res;
    for(int i = 0; i < nums.length;i++){
        combine(i + 1,nums);
    }
    res.add(new ArrayList<>());
    return res;
}

位运算

思路来自题解

对于[1,2,3][1,2,3]，可用三位二进制表示是否选择对应下标的数组元素。则有8种组合方式。

• 初始化数组长度nn，最终结果的长度res_len=1<<n，此处位运算表示的是2^n。
• 对于每种结果，对于i在遍历区间[0,res_len)中:
  • 初始化中间结果cur=[]
  • 从数组第一位到最后一位进行遍历，对于j在遍历区间[0,n)中：
    • 若满足条件i>>j&1，表示第j位是否为1，若满足，则将该位元素加入中间结果cur中
  • 将cur加入res
• 返回res

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int len = nums.length;
    int n = 1 << len;
    for(int i = 0;i < n;i++){
        List<Integer> cur = new ArrayList<>();
        for(int j = 0; j < len ; j++){
            if(((i >> j) & 1) == 1)
                cur.add(nums[j]);
        }
        res.add(cur);
    }
    return res;
}