https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
//https://leetcode.cn/problems/letter-combinations-of-a-phone-number/
//电话号码的字母组合
// class Solution {
// public:
//     string numtostr[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};

//     void combine(string &num_string, int di, string cbstr, vector<string> &ret){
//         if(di == num_string.size()){
//             ret.push_back(cbstr);
//             return;
//         }
//         int num = num_string[di] - '0';
//         string str = numtostr[num];
//         for(int i = 0; i < str.size(); ++i){
//             combine(num_string, di+1, cbstr+str[i], ret);
//         }
//     }

//     vector<string> letterCombinations(string num_string){
//         vector<string> ret;

//         if(num_string.empty())
//             return ret;

//         combine(num_string, 0, "", ret);

//         return ret;
//     }
// };
//解题思路：利用多路递归


// 解法二：利用深度优先搜索的思想
class Solution {
public:
    vector<string> ret;
    string path;
    string numstrs[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    
    vector<string> letterCombinations(string num_string){
        if(num_string.size() == 0)
            return ret;

        dfs(num_string, 0);
        return ret;
    }

    void dfs(string& num_string, int pos)
    {
        if(pos == num_string.size())
        {
            ret.push_back(path);
            return;
        }

        for(int i = 0; i < numstrs[num_string[pos]-'0'].size(); ++i)
        {
            path += numstrs[num_string[pos]-'0'][i];
            dfs(num_string,pos+1);
            path.pop_back();
        }
    }
};
--------------------------------------------------------------------------------------------------------
https://leetcode.cn/problems/generate-parentheses/description/
class Solution {
public:
    vector<string> ret;
    string path;
    int left = 0;
    int right = 0;

    vector<string> generateParenthesis(int n) {
        dfs(n);
        return ret;
    }
    
    void dfs(int n)
    {
        if(left < right || left > n || right > n)
            return;

        if(left == n &&  left == right)
        {
            ret.push_back(path);
            return;
        }

        path.push_back('(');
        left++;
        dfs(n);
        path.pop_back();
        left--;

        path.push_back(')');
        right++;
        dfs(n);
        path.pop_back();
        right--;
        
    }
};
// 有效的括号需要满足条件
// 1.左括号的数量 == 右括号的数量
// 2.对于任意一个子串，左括号的数量 >= 右括号的数量 
--------------------------------------------------------------------------------------------------------
https://leetcode.cn/problems/combinations/
// class Solution {
// public:
//     vector<vector<int>> ret;
//     vector<int> path;
//     int n;
//     int k;
//     vector<vector<int>> combine(int _n, int _k) {
//         n = _n;
//         k = _k;
//         dfs(1,0);
//         return ret;
//     }

//     void dfs(int num, int count)
//     {
//         if(count == k)
//         {
//             ret.push_back(path);
//             return;
//         }
//         for(int i = num; i <= n; ++i)
//         {
//             path.push_back(i);
//             dfs(i+1,count+1);
//             path.pop_back();
//         }
//     }
// };

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    int n;
    int k;
    vector<vector<int>> combine(int _n, int _k) {
        n = _n;
        k = _k;
        dfs(1);
        return ret;
    }

    void dfs(int begin)
    {
        if(path.size() == k)
        {
            ret.push_back(path);
            return;
        }
        for(int i = begin; i <= n; ++i)
        {
            path.push_back(i);
            dfs(i+1);
            path.pop_back();
        }
    }
};