C++算法学习心得六.回溯算法(2)

发布时间:2024年01月17日

1.组合总和(39题)

题目描述:

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

示例 1:

  • 输入:candidates = [2,3,6,7], target = 7,
  • 所求解集为: [ [7], [2,2,3] ]

回溯法: 如果是一个集合来求组合的话,就需要startIndex,如果是多个集合取组合,各个集合之间相互不影响,那么就不用startIndex,只是组合情况,与之前组合问题不一致的是该题可以重复选择,主要在于递归函数的startindex选取,

class Solution {
private: 
    vector<int>path;//路径
    vector<vector<int>>result;//结果集
    //回溯函数,需要参数:数组,目标,和,组合问题需要startindex来解决
    void backtracking(vector<int>& candidates,int target,int sum,int startindex){
        if(sum > target){
            return ;//如果和大于目标值直接返回
        }
        if(sum == target){
            result.push_back(path);//和和目标值相等,将路径加入结果集中
            return ;
        }
        //组合数组的遍历,遍历的集合树的宽度
        for(int i = startindex;i < candidates.size();i++){
            sum += candidates[i];//和求法
            path.push_back(candidates[i]);//路径加入
            backtracking(candidates,target,sum,i);//递归
            path.pop_back();//回溯
            sum -= candidates[i];//回溯
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtracking(candidates,target,0,0);
        return result;
    }
};

减枝操作:对总集合排序之后,如果下一层的sum(就是本层的 sum + candidates[i])已经大于target,就可以结束本轮for循环的遍历

class Solution {
private: 
    vector<int>path;//路径
    vector<vector<int>>result;//结果集
    //回溯函数,需要参数:数组,目标,和,组合问题需要startindex来解决
    void backtracking(vector<int>& candidates,int target,int sum,int startindex){
        if(sum > target){
            return ;//如果和大于目标值直接返回
        }
        if(sum == target){
            result.push_back(path);//和和目标值相等,将路径加入结果集中
            return ;
        }
        //组合数组的遍历,遍历的集合树的宽度,排序进行,如果sum+该值大于了目标值就不进行操作实现减枝
        for(int i = startindex;i < candidates.size() && sum + candidates[i] <= target;i++){
            sum += candidates[i];//和求法
            path.push_back(candidates[i]);//路径加入
            backtracking(candidates,target,sum,i);//递归
            path.pop_back();//回溯
            sum -= candidates[i];//回溯
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());//排序为了减枝
        backtracking(candidates,target,0,0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n),注意这只是复杂度的上界,因为剪枝的存在,真实的时间复杂度远小于此
  • 空间复杂度: O(target)

无数量要求终止条件发生改变,元素重复选用递归函数体现采用i而不是i+1,组合排序之后在进行减枝经常的操作

2. 组合总和II(40题)

题目描述:

给定一个数组?candidates?和一个目标数?target?,找出?candidates?中所有可以使数字和为?target?的组合。

candidates?中的每个数字在每个组合中只能使用一次。

说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。

  • 示例?1:
  • 输入: candidates =?[10,1,2,7,6,1,5], target =?8,
  • 所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

回溯法:集合(数组candidates)有重复元素,但还不能有重复的组合,组合问题可以抽象为树形结构,那么“使用过”在这个树形结构上是有两个维度的,一个维度是同一树枝上使用过,一个维度是同一树层上使用过,树层去重的话,需要对数组排序,加一个bool型数组used,用来记录同一树枝上的元素是否使用过。

used[i - 1] == true,说明同一树枝candidates[i - 1]使用过
used[i - 1] == false,说明同一树层candidates[i - 1]使用过

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false,就说明:前一个树枝,使用了candidates[i - 1],也就是说同一树层使用过candidates[i - 1]

used[i - 1] == false 就是同一树层呢,因为同一树层,used[i - 1] == false 才能表示,当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。而 used[i - 1] == true,说明是进入下一层递归,去下一个数,所以是树枝上,sum + candidates[i] <= target为剪枝操作

class Solution {
private: 
    vector<int>path;//路径
    vector<vector<int>>result;//结果集
    //回溯函数,需要参数:数组,目标,和,组合问题需要startindex来解决
    void backtracking(vector<int>& candidates,int target,int sum,int startindex,vector<bool>& used){
        if(sum > target){
            return ;//如果和大于目标值直接返回
        }
        if(sum == target){
            result.push_back(path);//和和目标值相等,将路径加入结果集中
            return ;
        }
        //组合数组的遍历,遍历的集合树的宽度,排序进行,如果sum+该值大于了目标值就不进行操作实现减枝
        for(int i = startindex;i < candidates.size() && sum + candidates[i] <= target;i++){
            if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false){
                continue;//我们使用used数组来进行处理去重的逻辑,先排序,如果前一个值和后一个值相等,且用过数组i-1位置没用过,需要去重,也就是需要在树层来进行操作,
            }
            sum += candidates[i];//和求法
            path.push_back(candidates[i]);//路径加入
            used[i] = true;//使用过变为true
            backtracking(candidates,target,sum,i+1,used);//递归
            path.pop_back();//回溯
            sum -= candidates[i];//回溯
            used[i] = false;//之后回溯
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool>uesd(candidates.size(),false);//定义使用过的数组
        sort(candidates.begin(),candidates.end());//排序为了减枝
        backtracking(candidates,target,0,0,uesd);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

3.分割回文串(131题)

题目描述:

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。

返回 s 所有可能的分割方案。

示例: 输入:?"aab" 输出: [ ["aa","b"], ["a","a","b"] ]

回溯法:切割问题类似组合问题,

  • 组合问题:选取一个a之后,在bcdef中再去选取第二个,选取b之后在cdef中再选取第三个.....。
  • 切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后在cdef中再切割第三段.....。

递归用来纵向遍历,for循环用来横向遍历,切割线(就是图中的红线)切割到字符串的结尾位置,说明找到了一个切割方法。需要startIndex,因为切割过的地方,不能重复切割,和组合问题也是保持一致的?

切割线切到了字符串最后面,说明找到了一种切割方法,此时就是本层递归的终止条件,[startIndex, i] 就是要截取的子串,切割过的位置,不能重复切割,所以,backtracking(s, i + 1); 传入下一层的起始位置为i + 1

class Solution {
private:
    vector<vector<string>>result;//结果集,注意里面的存放形式
    vector<string>path;//路径也是如此
    //回溯函数,注意参数,这里需要startindex作为集和选取组合类似操作,都是在一个集和选取需要startindex
    void backtracking(const string& s,int startindex){
        //如果起始位置已经大于s的大小,说明已经找到了一组分割方案了
        if(startindex >= s.size()){
            result.push_back(path);//终止条件,我们需要把找到的回文子串加入结果当中
            return;
        }
        //这个仍需要遍历树的宽度,也就是集和下标开始位置
        for(int i = startindex;i < s.size();i++){
            //判断是否是回文子串,注意下标从,startindex开始到I结束
            if(ispalindrome(s,startindex,i)){
                string str = s.substr(startindex,i - startindex + 1);//我们选取子串,
                path.push_back(str);//加入到路径中
            }else{
                continue;
            }
            backtracking(s,i+1);//递归,注意这里和组合一样的原理使用
            path.pop_back();//回溯  
        }
    }
    //回文子串判断函数,通过双指针的写法来实现,字符串的下标形式来完成
    bool ispalindrome(const string& s,int start,int end){
        //
        for(int i = start,j = end;i < j;i++,j--){
            if(s[i] != s[j]){
                return false;//字符串字符不等则返回错
            }
        }
        return true;
    }
public:
    vector<vector<string>> partition(string s) {
        result.clear();
        path.clear();
        backtracking(s,0);//回溯函数调用
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n^2)

4.复原IP地址(93题)

题目描述:

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

有效的 IP 地址 正好由四个整数(每个整数位于 0 到 255 之间组成,且不能含有前导 0),整数之间用 '.' 分隔。

例如:"0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址,但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例 1:

  • 输入:s = "25525511135"
  • 输出:["255.255.11.135","255.255.111.35"]

回溯法:?切割问题就可以使用回溯搜索法把所有可能性搜出来,切割问题可以抽象为树型结构,

startIndex一定是需要的,因为不能重复分割,记录下一层递归分割的起始位置。还需要一个变量pointNum,记录添加逗点的数量。递归调用时,下一层递归的startIndex要从i+2开始(因为需要在字符串中加入了分隔符.)回溯的时候,就将刚刚加入的分隔符.?删掉就可以了,pointNum也要-1。

class Solution {
private:
    vector<string>result;//结果集,需要接收字符串
    //我们定义一个回溯函数,参数startindex,句号
    void backtracking(string& s,int startindex,int pointnum){
        //如果句号三个,三个句号四段,所以可以实现收割结果
        if(pointnum == 3){
            //判断是否合法,第四段,如果合法就加入结果中
            if(isvalid(s,startindex,s.size()-1)){
                result.push_back(s);//将修改的字符串加入结果中
            }
            return;
        }
        //组合和切割问题类似的startindex,
        for(int i = startindex;i < s.size();i++){
            //如果合法,我们开始对其操作
            if(isvalid(s,startindex,i)){
                s.insert(s.begin()+i+1,'.');//记得在开始+i位置+1加入.
                pointnum++;//句号要增加操作
                backtracking(s,i+2,pointnum);//注意这里需要i+2,是因为有个.存在
                s.erase(s.begin()+i+1);//回溯
                pointnum--;//回溯
            }else break;//不合法,退出
        }
    }
    //判断是否合法
    bool isvalid(const string& s,int start,int end){
        if(start > end){
            return false;//
        }
        if(s[start] == '0' && start != end){
            return false;//0开头的数字不合法
        }
        int num = 0;
        for(int i = start;i <= end;i++){
            if(s[i] < '0' || s[i] > '9'){
                return false;//遇到非数字字符不合法
            }
            num = num*10 + (s[i] - '0');//获取当前数字
            if(num > 255){
                return false;//如果大于255了不合法
            }
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        result.clear();
        if (s.size() < 4 || s.size() > 12) return result;//减枝操作
        backtracking(s,0,0);//回溯
        return result;
    }
};
  • 时间复杂度: O(3^4),IP地址最多包含4个数字,每个数字最多有3种可能的分割方式,则搜索树的最大深度为4,每个节点最多有3个子节点。
  • 空间复杂度: O(n)

?5.子集(78题)

题目描述:

给定一组不含重复元素的整数数组?nums,返回该数组所有可能的子集(幂集)。

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

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

回溯法:组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点,子集也是一种组合问题,因为它的集合是无序的,既然是无序,取过的元素不会重复取,写回溯算法的时候,for就要从startIndex开始,而不是从0开始,求取子集问题,不需要任何剪枝!因为子集就是要遍历整棵树。

class Solution {
private:
    vector<int>path;
    vector<vector<int>>result;
    void backtracking(vector<int>& nums,int startindex){
        result.push_back(path);//别忘了这个
        if(startindex > nums.size()){
            return;//终止条件
        }
        for(int i = startindex;i < nums.size();i++){
            path.push_back(nums[i]);//加入路径
            backtracking(nums,i+1);//递归
            path.pop_back();//回溯
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};
  • 时间复杂度: O(n * 2^n)
  • 空间复杂度: O(n)

总结:?

组合总和:这里是一个集合但是元素可以重复选取,一个集合startindex,两个集合就是index,只不过不一样的是递归函数传参是i,就可以实现,注意减枝操作可以在树的宽度遍历变量做文章,对i进行限制,但是需要对数组进行排序

组合总和II:集合中有重复元素,但是结果中不可以出现重复,所以设计了去重的操作,这里我们使用一个数组去记录树层的是否使用了,布尔类型数据,我们依然需要排序,然后再对数组进行判断,如果相邻两个元素相等,且是树层情况下,那么不做操作,回溯也需要对判断数组进行回溯

分割回文串:切割问题类似组合问题,切割线就是startindex,切割字符串就是【startindex,i】,我们需要截取子串,回溯和组合类型相似,从i+1开始,注意回文子串判断函数的写法,

复原IP地址:这里我们做的复原Ip,需要考虑,终止条件,我们定义句号,加入三个句号就处理结束,然后需要判断是否切割的合法,合法加入结果,如果切割合法我们进行递归和回溯操作,还要写一个判断是否合法的函数,考虑各种非法情况来写相应的处理,

子集: 子集和组合问题最大区别在于,组合问题是查找叶子节点的,但是子集问题需要将所有结果返回,也需要startindex,来操作

文章来源:https://blog.csdn.net/weixin_55605689/article/details/135612147
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。