首页 > 其他分享 >leetcode78 子集

leetcode78 子集

时间:2024-11-26 16:33:25浏览次数:5  
标签:used nums int leetcode78 List dfs 子集 ans

leetcode78 子集

image-20241126152016861

思路:深度优先搜索回溯

分析此类问题可以先用树形结构模拟代码逻辑。

image-20241126152702898

那么根据这个解答树,首先我们的回溯搜索函数应该由这么几部分组成

  1. 将搜索获得的答案加入到res中。
  2. for循环遍历搜索下一个元素(比如在初始列表为空的时候,第一位可以选1,2,3显然需要通过循环实现)但是这道题要求的是解集,可以用一个参数currentNum记录下一步循环递归从哪里开始,保证不重复。
  3. for循环每次dfs后,回溯到原先状态进行下一次dfs。

那么需要哪些参数呢?

基础参数:int nums[],List<Integer> a,List<List<Integer>> ans

此外我们需要一个回溯逻辑,在dfs执行时改变状态,在dfs递归代码执行结束后回到原状态。所以我们需要几个参数来记录完整的原先状态。

回溯参数:boolean[] used,int currentNum

由此代码如下:

public void dfs(int nums[],List<Integer> a,List<List<Integer>> ans,boolean[] used,int currentNum){
    //1.将列表加入到ans中
    ans.add(new ArrayList<>(a));
    //2.递归
    for (int i = currentNum; i < nums.length; i++) {
        if (used[i]==false){
            a.add(nums[i]);
            used[i]=true;
            dfs(nums,used,i,a,ans);
            //3.回溯
            used[i]=false;
            a.remove(a.size()-1);
        }
    }
}
class Solution {
    public void dfs(int[] nums,boolean[] used,int currentNum,List<Integer> a,List<List<Integer>> ans){
        ans.add(new ArrayList<>(a));
        //这里非常关键不能add a,因为如果add a的话那么存的就是a的地址,最后ans里全都是a
        for (int i = currentNum; i < nums.length; i++) {
            if (used[i]==false){
                a.add(nums[i]);
                used[i]=true;
                dfs(nums,used,i,a,ans);
                used[i]=false;
                a.remove(a.size()-1);
            }
        }
    }
    public List<List<Integer>> subsets(int[] nums) {
        int len=nums.length;
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> a=new ArrayList<>();
        boolean[] used=new boolean[len];
        for (int i = 0; i < len; i++) {
            used[i]=false;
        }
        dfs(nums,used,0,a,ans);
        return ans;
    }
}

注意,如果这题不是求子集,而是求由整数数组可以生成的所有列表,那么就不需要记录currentNum,代码如下

class Solution {
    public void dfs(int[] nums,boolean[] used,List<Integer> a,List<List<Integer>> ans){
        ans.add(new ArrayList<>(a));
        //这里非常关键不能add a,因为如果add a的话那么存的就是a的地址,最后ans里全都是a
        for (int i = 0; i < nums.length; i++) {
            if (used[i]==false){
                a.add(nums[i]);
                used[i]=true;
                dfs(nums,used,a,ans);
                used[i]=false;
                a.remove(a.size()-1);
            }
        }
    }
    public List<List<Integer>> subsets(int[] nums) {

        int len=nums.length;
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> a=new ArrayList<>();
        boolean[] used=new boolean[len];
        for (int i = 0; i < len; i++) {
            used[i]=false;
        }
        dfs(nums,used,a,ans);
        return ans;
    }
}

最终搜索结果如下
image-20241126162617883

标签:used,nums,int,leetcode78,List,dfs,子集,ans
From: https://www.cnblogs.com/vastjoy/p/18570450

相关文章

  • 子集和dp
    子集和dp用处统计n维偏序,但是每一维的大小只能是2。计算子集权值之和。实际上以上两种问题是等价的。例如目前有一个集合:101(其中1表示有某个物品,0表示没有)。那该集合包涵的子集有4个:101,100,001,000。现在要把这4个集合的权值加起来。按照第二种理解(用处),我们可以一位一位地......
  • 【题解】【子集枚举】—— PERKET
    【题解】【子集枚举】——PERKET[COCI2008-2009#2]PERKET题目描述输入格式输出格式输入输出样例输入#1输出#1输入#2输出#2输入#3输出#3提示数据规模与约定说明1.思路解析2.AC代码[COCI2008-2009#2]PERKET通往洛谷的传送门题目描述Perket是一种流行......
  • 子集反演 & sos dp 学习笔记
    子集反演&sosdp学习笔记子集反演设\(g(S)\)表示集合\(S\)的答案,\(f(S)\)为\(S\)的子集的答案和。根据定义:\[f(S)=\sum_{T\inS}g(T)\]子集反演就是:\[g(S)=\sum_{T\inS}(-1)^{|S|-|T|}f(T)\]本质上就是容斥原理,可感性理解,证明略(给你你也记不住)。于是便可以通......
  • Day 21 回溯法part03| LeetCode 93. 复原 IP 地址,78.子集,90.子集II
    93.复原IP地址93.复原IP地址classSolution{List<String>res=newArrayList<>();publicList<String>restoreIpAddresses(Strings){backtracking(s,0,0);returnres;}voidbacktrack......
  • JAVA学习-练习试用Java实现“子集”
    问题:给定一个整数数组nums,数组中的元素互不相同。返回该数组所有可能的子集(幂集)。解集不能包含重复的子集。你可以按任意顺序返回解集。示例1:输入:nums=[1,2,3]输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例2:输入:nums=[0]输出:[[],[0]]提示:1<=num......
  • leetcode刷题day24|回溯算法Part03(93.复原IP地址、78.子集、90.子集II)
    93.复原IP地址思路:这个题和131.分割回文串一样都是对字符串进行分割,只不过这个子字符串判断时是看是不是0-225之间的数字。回溯三部曲:1、递归函数参数:全局变量:String数组result存放结果集。递归函数参数:原字符串;startIndex,因为切割过的地方不能重复切割,和组合问题是一样......
  • VUE 分组取最大,生成子集合
    //分组函数 constgroupByAge=(docs:TOSDepositoryDTO[]):Record<number,TOSDepositoryDTO[]>=>{ returndocs.reduce((acc,d)=>{  if(!acc[d.approvalId])acc[d.approvalId]=[];  acc[d.approvalId].push(d);  returnacc; },{}asR......
  • 早上好祝福语暖心句子集锦,今天精美的祝福图片大全
    一朝相识一生缘,永生牵挂在心间,岁月匆匆又一天,清晨祝福在身边,千言万语汇一句,安康幸福每一天。早上好!岁月告诉我们,有一颗宽容的心,会健康一辈子。有一颗善良的心 ,会平安一辈子。有一颗童心,会年轻一辈子。 上午吉祥!人生一世,有春风得意,有苦甜相依,有喜乐相伴,有烦忧挠人,只要静下......
  • 【Leetcode:LCR 101. 分割等和子集 + 递归 + 记忆化搜索 + dp】
    ......
  • 回溯——7.子集II
    力扣题目链接给定一个可能包含重复元素的整数数组nums,返回该数组所有可能的子集(幂集)。说明:解集不能包含重复的子集。示例:输入:[1,2,2]输出:[[2],[1],[1,2,2],[2,2],[1,2],[]]解题思路总结:排序:首先对数组进行排序,便于之后的重复元素跳过处理。回溯法:通过递归遍......