[C++知识库]C++回溯算法之一

/*
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
*/


#include <iostream>
#include<string>
#include<algorithm>

using namespace std; 

int main()

{
    string str = "abbaca";
    string result;
    for (char s : str)
    {
        if (result.empty()||result.back()!=s)
        {
            result.push_back(s);
        }
        else
        {
            result.pop_back();
        }
    }
  
    cout << result;

}

/*
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:

输入: n = 4, k = 2
输出:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

*/


#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
//#include<map>
//#include<set>
//#include<unordered_set>
#include<stack>

using namespace std; 
class Solution {
private:
    vector<vector<int>> result; // 存放符合条件结果的集合
    vector<int> path; // 用来存放符合条件结果
   
    void backtracking(int n, int k, int startIndex=1)
    {
        if (path.size() == k)
        {          
            result.push_back(path);
            return;
        }
         for (int i = startIndex; i <= n; i++) 
        {
            path.push_back(i);              // 处理节点 
            backtracking(n, k, i + 1);      // 递归
            path.pop_back();                // 回溯，撤销处理的节点
        }
    }
public:
    vector<vector<int>> combine(int n, int k)
    {    
        backtracking(n, k);
        return result;
    }
};

/*
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

所有数字都是正整数。
解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]

示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]
*/


#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<stack>

using namespace std; 
class Solution {
private:
    vector<vector<int>> result; // 存放结果集
    vector<int> path; // 符合条件的结果
    int comback = 0;
    int into = 0;
    // targetSum：目标和，也就是题目中的n。
    // k：题目中要求k个数的集合。
    // sum：已经收集的元素的总和，也就是path里元素的总和。
    // startIndex：下一层for循环搜索的起始位置。
    void backtracking(int targetSum, int k, int sum, int startIndex=1) {
        if (path.size() == k)        // 如果path.size() == k 但sum != targetSum 直接返回
        {
            if (sum == targetSum)
            {
                result.push_back(path);
            }
            
            return;                   //递归中的retuen相当于for循环中的break，直接中断此次递归
                                            
        }
        for (int i = startIndex; i <= 9; i++)   //递归的次数是由for'循环来控制，
        {                                      //结束递归有2种方式，1-不符合条件reruen。 2-for到达循环终止条件自动结束递归
                                                //三重递归加自身for循环，形成四重循环。 最后一重递归由return终止，前面三层
                                                //均有for循环参数来控制范围
            sum += i; // 处理
            path.push_back(i); // 处理
            into++;
            cout << "调用递归==" << into << endl;
            backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndex
             comback++;
            cout << "回溯==" << comback << endl;
            sum -= i; // 回溯
            path.pop_back(); // 回溯
        }
    }

public:
    vector<vector<int>> combinationSum3(int targetSum, int k) {
      
        backtracking(targetSum, k, 0);
        return result;
    }
};

int main()
{
   Solution Test;
    auto num=Test.combinationSum3(9,3);
   
    for (auto s : num) {
        for (auto c : s) { cout << c ; }
        cout << endl;
    };

}

*
题目链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
*/


#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
//#include<map>
//#include<set>
//#include<unordered_set>
#include<stack>

using namespace std; 

// 版本一
class Solution 
{
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string str;
        
    void backtrack(string &digits,int index=0)
    {
        if (index==digits.size())   //使用index来控制存储的时机
        {
            result.push_back(str);
            return;
        }
      
        int num=digits[index] - '0';
        string letter = letterMap[num];
        for (size_t i = 0; i < letter.size(); i++)
        {
            str.push_back(letter[i]);
            backtrack(digits,index+1);      //递归,递归也可以理解为一层for循环，本质上差不多，写法上有些不同
            str.pop_back();                 //回溯
        }
    
    }

    vector<string> combination(string digits)
    {   
       
        backtrack(digits);                        //index默认为0，所以可以不传入
        return result;
    }

};

int main()
{
    Solution Test;  
   auto num= Test.combination("23"); 

    for (auto s : num) {
       // for (auto c : s) 
        { cout << s ; }
        cout << endl;
    };
  
}

/*
题目链接：https://leetcode-cn.com/problems/palindrome-partitioning/

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

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

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


#include <iostream>
#include<string>
#include<algorithm>
#include<vector>


using namespace std; 
class Solution
{
public:
    vector<vector <string>> result;
    vector<string> str;

    void backtracking(const string &s,int index=0) 
    {
        if (index>=s.size())		//控制递归的深度，始终不超过字符串大小
        {
            result.push_back(str);
            return;
        }

        for (int i = index; i < s.size(); i++)
        {
            if (palindrome(s, index, i))
            {
                str.push_back(s.substr(index,i-index+1));	//找到会问字符
            }
            else
            {
                continue;
            }
            backtracking(s, index + 1);	//递归调用，下一层递归从+1位置开始查找会问
            str.pop_back();       	//回溯
        }
    }

    bool palindrome(const string sl,int start,int end)//判断是否回文
    {
        for (int i = start,j=end; i < j; i++,j--)
        {
            if (sl[i] != sl[j])
            {
                return false;
            } 
        }
        return true;
    }

    vector<vector<string>> partition(string s)
    {
        backtracking(s);
        return result;
    }
};

int main()
{
    Solution Test;
    auto num = Test.partition("aab");

    for (auto s : num) {
        for (auto c : s)  { cout << c <<ends; }
        cout << endl;
    };
  
  
}