递归与回溯算法整理（一）

递归 与 回溯

	回溯其实是一种暴力解决问题的方式， 对于问题规模大于20以上的数据，个人计算机将不能处理。

问题分析 ：

对于 0 1 * # 不用考虑

对于 2～ 9 每个数字都有3中情况。 那么对于一个数字串 ，将面临多种组合现象 。

我们可以 画树形图。

树形图会很容易发现这是一个递归问题。
对于每个问题，又形成一个和原问题类似的问题。（不存在重叠）

那么 我们可以递归来处理

class Solution {
public:
    vector<string> table = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
   //原问题入口
   vector<string> letterCombinations(string digits) {
        vector<string> res;
        func(res, "", digits, 0);
        return res;
    }

 // 递归处理
    void func(vector<string> &res, string str, string &digits, int i){
        if(i == digits.size()){
            if(str.size() > 0) res.push_back(str);
            return;
        }
        
        else{//进进出出
        					// -2 是因为不考虑  0 和 1 
            string s = table[digits[i] - '2'];//拿到当前数字对应字母可能
            for(int j = 0; j < s.size(); ++j){
                str.push_back(s[j]);//放进去
                func(res, str, digits, i+1);
                str.pop_back();//取出来
            }
        }
    }
};

上边这个看着有点凌乱，来来来，整理下代码

来看个精简版的

class Solution {
private:
    vector<string> letter={"abc","def","ghi","jkl", "mno","pqrs", "tuv", "wxyz"};

private:
    //index  代表当前处理到第几个字符了
    void subQuestion(vector<string>& res, string& digits,int index, const string& dest)
    {
        if (index == digits.size())
        {
            res.push_back(dest);
            return;
        }
        //获取当前字符串 ， 下标由digits[index] -'2'决定
        string tmp = letter[digits[index] - '2'];
        for(int i=0; i<tmp.size(); ++i)
            subQuestion(res, digits, index+1, dest+tmp[i]);
    }

public:
    vector<string> letterCombinations(string digits) {
    vector<string> res;//保存返回
    int n =digits.size();
     if(n == 0) return  res;  
         subQuestion(res, digits, 0, "");
     return res;
    }
};

再想想思路 ，其实 回溯法就是一种暴力，我们完全可以用多重循环来解决。

有的时候没思路，就只能用暴力 ，那么考虑下回溯。

回溯的时间复杂度是 O (2^N)

全排列问题：

	力扣  46 题  ：给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

思路 还是 画 树型图 的办法：

画图之后一目了然。

//下面这个题 的解法就很好的体现了回溯的想法。 虽然递归本来就有回溯的意思 ，但是， 有必要时，我们还是得注意变量的回溯。

因为排列中的元素是不能冲突的， 所以，我们还是得回溯标记状态。

class Solution {
private: 
    vector<bool> memo;

private:
    void subQuestion(vector<vector<int>> & res, vector<int>nums, vector<int>& sub, int n)    
    {
        if(n == nums.size())  
        {
            res.push_back(sub);
            return ;
        }    

        //注意，这里每一层都会从这里开始，那么我们得避免重复排列
        //换句话说： 每来到一个数字前，判断这个数字是在本排列出现过
        //那么我们可以使用一趟遍历来查找。可是导致时间复杂变高
        //我们采用辅助数组标记已经用过的数字。
        for(int i=0; i < nums.size(); ++i)
        if(!memo[i])
        {
            memo[i] = true;
            sub.push_back(nums[i]);
            subQuestion(res, nums, sub, n+1);
            sub.pop_back();//回退（换个数字排列）
            memo[i] = false;
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n == 0)  return res;
        
        vector<int> sub;
        memo = vector<bool>(n,false);
        subQuestion(res, nums, sub, 0);
        return res;
    }
};

这道题还是和 之前的题不相同的。因为这里涉及到了吞下与吐出的考虑。

最后再体会一下辅助数组的妙处。