回溯算法

伪代码1：

result;//用于存放结果集

backTracking()
{
    if(满足结束条件）
    {
        将结果添加到结果集中；
        return;
    }

    for(选择in选择列表)
    {
        修改；
        backTracking();//回溯
        回改；
    }
}

LeetCode46-全排列：给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。

class Solution {
public:
    vector<vector<int>> result;

    vector<vector<int>> permute(vector<int>& nums) 
    {
        backtracking(0,nums);//回溯
        return result;
    }

    //回溯
    void backtracking(int k,vector<int>& nums)
    {
        //if(满足结束条件)
        if(k==nums.size()-1)
        {
            result.push_back(nums);
            return;
        }

        //for(选择in选择列表)
        for(int i=k;i<nums.size();++i)
        {
            swap(nums[i],nums[k]);//修改
            backtracking(k+1,nums);//回溯
            swap(nums[i],nums[k]);//回改
        }
    }
};

LeetCode51-N皇后：将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击（任何两个皇后都不能处于同一条横行、纵行或斜线上）。给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

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

    vector<vector<string>> solveNQueens(int n) 
    {
        if(n==0)
            return {};

        int row=0;//行数
        //矩阵result的某一行
        vector<string> board(n,string(n,'.'));
        //列colomn，左斜ldiag，右斜rdiag；记录是否存在皇后
        vector<bool> colomn(n,false),ldiag(2*n-1,false),rdiag(2*n-1,false);

        BackTracking(colomn,ldiag,rdiag,board,row,n);//回溯

        return result;
    }

    //回溯
    void BackTracking(vector<bool>& colomn,vector<bool>& ldiag,vector<bool>& rdiag,vector<string>& board,int row,int n)
    {
        //满足结束条件已经遍历完了所有的行
        if(row>=n)
        {
            result.push_back(board);
            return;
        }
   
        for(int j=0;j<n;++j)//逐行判断，并插入皇后
        {
            if(colomn[j]||ldiag[row+j]||rdiag[n-row+j-1])
                continue;

            board[row][j]='Q';
            colomn[j]=ldiag[row+j]=rdiag[n-row+j-1]=true;//修改

            BackTracking(colomn,ldiag,rdiag,board,row+1,n);//回溯
            
            board[row][j]='.';
            colomn[j]=ldiag[row+j]=rdiag[n-row+j-1]=false;//回改
        }    
    }
};

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

class Solution {
public:
    vector<vector<int>> result;

    vector<vector<int>> combine(int n, int k) 
    {       
        vector<int> comb(k,0);
        int count=0;

        BackTracking(comb,count,n,k,1);//回溯

        return result;
    }

    void BackTracking(vector<int>& comb,int count,int n,int k,int pos)
    {
        //if(满足结束条件)，已经选了k个数
        if(count==k)
        {
            result.push_back(comb);
            return;
        }

        //for(选择in选择列表)
        for(int i=pos;i<=n;++i)
        {
            comb[count++]=i;//修改
            BackTracking(comb,count,n,k,i+1);//回溯
            --count;//回改
        }
    }
};

伪代码2：

result;//用于存放结果集

backTracking()
{
    if(满足结束条件）
    {
        将结果添加到结果集中；
        return;
    }

    for(选择in选择列表)
    {
        if(满足条件）
        {
            修改；
            backTracking();//回溯
            回改；
        }
        else
        {
          break;
        } 
    }
}

LeetCode93-复原IP地址：给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。

class Solution {
public:
    vector<string> result;

    vector<string> restoreIpAddresses(string s) 
    {
        backtracking(s, 0, 0);//回溯

        return result;
    }
    
    //回溯
    void backtracking(string& s, int startIndex, int pointNum)
    {
        //if(满足结束条件)，点的数量已经够了
        if(pointNum == 3)
        {
            //判断剩下的字符串是否符合条件
            if(isValid(s, startIndex, s.size() - 1))
                result.push_back(s);

            return;
        }

        //for(选择in选择列表)
        for(int i = startIndex; i < s.size(); i++)
        {
            if(isValid(s, startIndex, i))//i不同表示从不同的位置进行分割
            {
                s.insert(s.begin() + i + 1, '.');
                pointNum++;//修改

                backtracking(s, i + 2, pointNum);//回溯

                pointNum--;
                s.erase(s.begin() + i + 1);//回改
            }
            else 
                break;
        }
    }
    
    //判断该段字符串是否有效
    bool isValid(const string& s, int start, int end)
    {
        //s[start...end]以0开头并且不是0（含前导项0）  或者  起止范围不符合条件
        if(s[start] == '0' && start != end||start > end)
            return false;

        int num = 0;
        for(int i = start; i <= end; i++)
        {
            if(s[i] > '9' || s[i] < '0')//含有其他字符
                return false;

            num = num * 10 + (s[i] - '0');//计算该段字符串表示的数字的大小
            if(num > 255)
                return false;
        }

        return true;
    }

};

LeetCode131-分割回文串：给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。

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

    vector<vector<string>> partition(string s) 
    {
        if (s.empty())
            return {};

        vector<string> ans;

        backTracking(s, ans, 0);

        return result;
    }

    void backTracking(const string& s,  vector<string>& ans, int pos)
    {
        //if(满足结束条件)
        if (pos >= s.length())
        {
            result.push_back(ans);
            return;
        }

        //for(选择in选择列表)
        for (int i = pos; i < s.length(); ++i)
        {
            string currStr = s.substr(pos, i-pos+1);

            if (IsPalindrome(currStr))//是回文串，则进行回溯
            {
                ans.push_back(currStr);//修改
                backTracking(s, ans, i+1);//回溯
                ans.pop_back();//回改
            }
        }
    }

    //判断当前字符是否是回文：双指针做法
    inline bool IsPalindrome(const string& currStr)
    {
        int l = 0;//左指针
        int r = currStr.size()-1;//右指针
        // 双指针，从字符串两边收缩去检查
        while(l < r)
        {
            if (currStr[l] != currStr[r]) return false;
            l++; r--;
        }
        return true;
    }
};