首页 > 其他分享 >代码随想录训练营第23天|回溯去重

代码随想录训练营第23天|回溯去重

时间:2024-09-09 19:53:59浏览次数:15  
标签:return target 23 int 随想录 vector candidates result 回溯

39. 组合总和

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum=0;

    void dfs(vector<int>& candidates, int target, int startIdx){
        if(sum==target){
            result.push_back(path);
            return;
        }
        if(sum>target)
            return;
        for(int i=startIdx; i<candidates.size(); i++){
            path.push_back(candidates[i]);
            sum+=candidates[i];
            dfs(candidates,target,i);
            sum-=candidates[i];
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        dfs(candidates,target,0);
        return result;
    }
};

因为可以重复选取,所以递归的下一个数字的搜索起点(startIdx)是i,而非i+1。

40. 组合总和 II

class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    int sum=0;

    void dfs(vector<int>& candidates, int target, int startIdx){
        if(sum==target){
            result.push_back(path);
            return;
        }
        if(sum>target)
            return;
        for(int i=startIdx; i< candidates.size();i++){
            path.push_back(candidates[i]);
            sum+=candidates[i];
            dfs(candidates,target,i+1);
            sum-=candidates[i];
            path.pop_back();
            while(i+1<candidates.size()&&candidates[i+1]==candidates[i])
                i++;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,target,0);
        return result;
    }
};

回溯之后,相同数值的元素直接跳过,实现本层去重功能。 

 131. 分割回文串

class Solution {
public:
    vector<vector<string>> result;
    vector<string> path;

    bool check(string& s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s[left++] != s[right--])
                return false;
        }
        return true;
    }

    void dfs(string& s, int stardIdx) {
        if (stardIdx == s.length()) {
            result.push_back(path);
            return;
        }
        for (int endIdx = stardIdx + 1; endIdx <= s.length(); endIdx++) {
            string sub = s.substr(stardIdx, endIdx - stardIdx); //[startIdx,endIdx) 左闭右开
            if (check(sub)) {
                path.push_back(sub);
                dfs(s, endIdx);
                path.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return result;
    }
};

子串在合法的情况下,才会尝试递归新的起点位置(startIdx),直到已经切分到末尾,收集结果。

标签:return,target,23,int,随想录,vector,candidates,result,回溯
From: https://blog.csdn.net/jiyisuifeng1991/article/details/141914333

相关文章

  • 2023年电赛D题 信号调制方式识别与参数估计装置 中对2PSK信号的解调的方案分享
     前言   由于做过此题,且PSK信号在本题中最难解调,所以突发其想写篇文章给寻解之人,由于本人处于大三阶段,知识储备难免有不足,多多包容,欢迎讨论交流。 正文   不多bb直接开始。首先我们得搞清楚PSK解调为什么难。第一,PSK解调只能用相干解调,ASK\PSK则可以采用相干......
  • 代码随想录day9-栈和队列1
    题目1232.用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现MyQueue类:voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的元素booleanempty()如......
  • HNU-2023电路与电子学-实验4
    写在前面:本次实验是完成cpu设计的时序部件,整体难度较小但涉及板块较多,细心完成就能顺利通过全部测评一、实验目的1.了解模型机中SM的作用。2.熟悉指令寄存器、状态寄存器、指令计数器、寄存器的工作原理3.学会使用VERILOG语言设计时序电路。二、实验内容1.用VER......
  • P7230 题解
    P7230思路对每个左端点维护右端点\(res_i\)。操作形如删去一个数再加入一个数。如果删掉\(p\)上的\(a_p\),找到左右最近的\(l,r\)使得\(a_l=a_r=a_p\)。那么\(res_{l+1},\dotsb,res_p\)对\(r\)取max。实际上要维护\(\maxres_i-i+1\),因为\(res_i\)单调,所以相当于......
  • 代码随想录day8-字符串2
    题目1151.反转字符串中的单词*给你一个字符串s,请你反转字符串中单词的顺序。单词是由非空格字符组成的字符串。s中使用至少一个空格将字符串中的单词分隔开。返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。注意:输入字符串s中可能会存在前导空格、尾......
  • 河南省12123公安厅临牌打印如何下载打印控件
    公安交通管理综合应用平台打印控件安装失败,河南省公安厅临牌打印如何下载打印控件,12123临牌系统怎么安装打印控件?   关于“12123河南省公安厅临牌打印如何下载打印控件怎么安装打印控件”的问题,实际上,交管12123APP主要用于在线申请临时号牌、查询车辆信息、处理交通违......
  • 代码随想录day55 || 图论5
    并查集197图中是否存在有效路径varfather[]intfuncvalidPath(nint,edges[][]int,sourceint,destinationint)bool{ //使用并查集算法,涉及到的操作,包括init,find,issample,join father=make([]int,n) fori,_:=rangefather{//init father[i]=i }......
  • LeetCode 239. 滑动窗口最大值(滑动窗口)
    题目:239.滑动窗口最大值思路:用一个双端队列来保存滑动窗口内的值按大到小排序,时间复杂度0(n)。细节看注释classSolution{public:vector<int>maxSlidingWindow(vector<int>&nums,intk){ //元素值是nums的下标,满足nums值按大到小排序deque<in......
  • 题解 GZOI2023D2B【乒乓球】
    4s,512M题目描述Alice和Bob在打乒乓球,乒乓球比赛的规则是这样的:一场比赛中两位选手将进行若干局比赛,选手只需要赢得\(X\)局比赛就宣告其胜利;每局比赛中两位选手将进行若干盘比赛,选手只需要赢得\(Y\)盘比赛就宣告其胜利;每盘比赛中两位选手将进行乒乓球对决,有且仅有一位选......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了,这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\),由o、-、x组成。判断\(S\)是否符合下列条件:\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......