https://leetcode.cn/problems/generate-parentheses/description/
class Solution {
public:
    string path;
    vector<string> ret;
    vector<bool> check;
    vector<string> generateParenthesis(int n) {
        string str;
        for(int i=0; i<n; ++i)
        {
            str+='(';
        }
        for(int i=0; i<n; ++i)
        {
            str+=')';
        }
        check = vector<bool>(2*n, false);
        dfs(str);
        return ret;
    }
    void dfs(string& s)
    {
        if(path.size()==s.size())
        {
            if(Check_path()) ret.push_back(path);
            return;
        }

        for(int i=0; i<s.size(); ++i)
        {
            if(check[i]) continue;// 剪枝
            check[i]=true;
            path.push_back(s[i]);
            dfs(s);
            check[i]=false;
            path.pop_back();
            
            while(i+1<s.size() && s[i+1]==s[i]) i+=1;
        }

    }
    bool Check_path()
    {
        int count=0;
        for(char ch:path)
        {
            if(ch==')' && count==0) return false;
            
            if(ch=='(') count+=1;
            else if(ch==')') count-=1;
        }
        
        return count==0;
    }
};

https://leetcode.cn/problems/combinations/description/

class Solution {
public:
    vector<int> path;
    vector<vector<int>> ret;
    vector<vector<int>> combine(int n, int k) {
        vector<int> nums;
        for(int i=1; i<=n; ++i)
        {
            nums.push_back(i);
        }
        dfs(nums, 0, k);
        return ret;
    }
    void dfs(vector<int>& nums, int pos, int k)
    {
        if(path.size()==k)  // 出口
        {
            ret.push_back(path);
            return;
        }
        for(int i=pos; i<nums.size(); ++i)
        {
            path.push_back(nums[i]);
            dfs(nums, i+1, k);
            path.pop_back();
        }
    }
};