LeetCode078之子集（相关话题：组合排列）

题目描述

给你一个整数数组 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 的序列 a 的所有子序列，代码框架是这样的：

List<Integer> t = new ArrayList<Integer>();
void dfs(int cur, int n) {
    if (cur == n) {
        // 记录答案
        // ...
        return;
    }
    // 考虑选择当前位置
    t.add(cur);
    dfs(cur + 1, n, k);
    t.reomve(t.zise()-1);
 
    // 考虑不选择当前位置
    dfs(cur + 1, n, k);
}
 

代码实现

方法一

​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;
        //先遍历n位二进制,所有可能的组合
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            //再遍历nums数组,判断i对应二进制数位是否在mask的二进制数据位上存在
            for (int i = 0; i < n; ++i) {
                //1 << i可理解为i对应二进制上填1其余位填0
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }
}
 
​

方法二

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;
        }
        t.add(nums[cur]);
        dfs(cur + 1, nums);
        t.remove(t.size() - 1);
        dfs(cur + 1, nums);
    }
}

拓展应用

LeetCode 39. 组合总和

class Solution {
 
    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
 
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return ans;
 
    }
 
    //我们定义递归函数 dfs(target, combine, idx) 表示当前在 candidates 数组的第 idx 位，还剩 target 要组合
    public void dfs(int[] candidates,int target,int index) {
 
        if(index == candidates.length){
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(t));
            return;
        }
 
 
        if(candidates[index]<=target){
            t.add(candidates[index]);
            dfs(candidates,target-candidates[index],index);
            t.remove(t.size() - 1);
            dfs(candidates,target,index+1);
        }else{
            return;
        }
 
    }
 
 
}

 知识复习

1&1=1

1&0=0

0&0=0

 博主总结

应用拓展一定要自己写一遍才知道自己的思考盲点在哪