LetCode 22:Generate Parentheses의 귀환, 두 가지 해법을 거슬러 올라간다

Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
“((()))”, “(()())”, “(())()”, “()(())”, “()()()”
귀속

class Solution {
public:
    void unguarded_generate(vector<string> &result, string &curr, int m, int n)
    {
        // m,n '(',')' 
        if(m==0 && n==0)
        {
            result.push_back(curr);
            return;
        }
        if(m>0) //  m n
        {
            curr.push_back('(');
            unguarded_generate(result, curr, m-1, n);
            curr.pop_back();
        }
        if(m//  ), n-1 m<=n
        {
            curr.push_back(')');
            unguarded_generate(result, curr, m, n-1);
            curr.pop_back();
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string curr;
        curr.reserve(2*n);
        unguarded_generate(result, curr, n, n);
        return result;
    }
};

이 문제를 거슬러 올라가는 태그에 백트랙팅이 있어서 거슬러 올라가서 풀려고 했어요.사고방식은 선방'('후방')', 가득 차면 전편'('을 거슬러 올라가 맨 왼쪽으로 거슬러 올라가면 끝난다는 것이다.m는 놓지 않은 수량'('의 수량을 나타내고, n은 놓지 않은 수량')'의 수량을 나타내며, 정상적인 놓지 않은 과정에서 m는 반드시 n보다 작다.거슬러 올라가는 순환 조건 중 m>n-2가 있는데 뒤에++m, -n의 조작이 있기 때문에 m+1<=n-1, 즉 m<=n-2를 확보하고 조건이 충족되지 않으면 계속 순환해야 한다.귀속에 비해 귀속의 비용이 적고 효율이 비교적 높다.

class Solution
{
public:
    vector<string> generateParenthesis(int k)
    {
        vector<string> result;
        string curr;
        curr.reserve(2*k);
        int m=k,n=k;
        while(1)
        {
            while(m>0)
            {
                curr.push_back('(');
                --m;
            }
            while(n>0)
            {
                curr.push_back(')');
                --n;
            }
            result.push_back(curr);
            while(*curr.rbegin()==')' || m>n-2)
            {
                if(*curr.rbegin()=='(') ++m;
                else ++n;
                curr.pop_back();
                if(curr.size()==0) return result;
            }
            *curr.rbegin()=')';
            ++m;
            --n;
        }
    }
};