LeetCode 刷题笔记——递归与回溯的理解

- [LeetCode](https://leetcode.com/) 递归与回溯的区别解释： 

- [《关于递归与回溯比较通俗的方法》](http://blog.163.com/be_forceful/blog/static/234310099201451952331128/)
- [《回溯和递归区别》](https://blog.csdn.net/u014772862/article/details/51789015)答题思路与源码 

- [《leetcode 46. Permutations-全排列|回溯|递归|非递归》](https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51534048)
- [《刷题笔记3（关于Permutation需要知道的事）》](https://zhuanlan.zhihu.com/p/24523433)
- [《以Generate Parentheses为例，backtrack的题到底该怎么去思考？》](http://www.1point3acres.com/bbs/thread-172641-1-1.html)
- [《回溯法》](https://zhuanlan.zhihu.com/p/28340833) （内有福利）

int fac(int n) {
    if(n == 1) return n;
    else 
        return (n*fac(n - 1)); 
}

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res, dst;
        // 初始化字典映射
        unordered_map<int, string> dict;
        dict.insert(make_pair<int, string>(2, "abc"));
        dict.insert(make_pair<int, string>(3, "def"));
        dict.insert(make_pair<int, string>(4, "ghi"));
        dict.insert(make_pair<int, string>(5, "jkl"));
        dict.insert(make_pair<int, string>(6, "mno"));
        dict.insert(make_pair<int, string>(7, "pqrs"));
        dict.insert(make_pair<int, string>(8, "tuv"));
        dict.insert(make_pair<int, string>(9, "wxyz"));
        // 检查输入字符是否在 2 - 9 范围内
        for(int i = 0; i < digits.size(); ++i)
            if(digits[i] < '2' || digits[i] > '9') {
                vector<string> nullstrs;
                return nullstrs;
            }

        // 递归思路
        if(digits.size() > 1) {
            string sub_digits = digits.substr(1, digits.length() - 1);
            res = letterCombinations(sub_digits);
        }

        // 查找字符串首字母对应的所有字符
        string keystr = dict[digits[0] - '0'];
        if(digits.length() == 1) {
            for(int m = 0; m < keystr.length(); ++m) {
                string tmp = ""; tmp += keystr[m];
                dst.push_back(tmp);
            }
        }

        // 双重循环，将vector<string> 与 char 组合，形成一个新的 vector<string>
        for(int m = 0; m < keystr.length(); ++m) {
            for(int n = 0; n < res.size(); ++n) {
                string tmpstr = keystr[m] + res[n];
                dst.push_back(tmpstr);
            }
        }

        return dst;
    }
};

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

- 将集合分为两部分：挑选集合中任一个元素，以及剩余元素组成的子集；
- 对子集进行递归，返回一个集合；
- 将先前挑出来的元素放置在递归后返回的集合中；

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> >  res, dst;
        // nums 容量小于等于 1，立即返回
        if(nums.size() <= 1) {
            dst.push_back(nums);
            return dst;
        }
        // 遍历 nums 所有元素
        for(int i = 0; i < nums.size(); ++i) {
            // 将 nums 分离成一个元素，其他部分分为一个子集
            // num: 分离元素
            // set: 子集
            int num = nums[i];
            vector<int> set = nums; set.erase(set.begin() + i);
            // 递归
            res = permute(set);

            for(int j = 0; j < res.size(); ++j) {
                // subPermu: 递归结果的单一变量
                vector<int> subPermu = res[j];
                subPermu.push_back(num);
                dst.push_back(subPermu);
            }
        }
        return dst;
    }
};

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        backtrack_Parentheses("", res, n, n);
        return res;
    }

    void backtrack_Parentheses(string sublist, vector<string>& res, int left, int right) {
        if(left == 0 && right == 0) {
            res.push_back(sublist);
            return ;
        }
        if (left > right)
            return;
        if (left > 0)
            backtrack_Parentheses(sublist + "(", res, left - 1, right);
        if (right > 0)
            backtrack_Parentheses(sublist + ")", res, left, right - 1);
    }
};