모든 괄호 일치 생성Generate Parentheses

1146 단어
제목은leetcode에서 유래했다.
제목: 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:
		vector<string> generateParenthesis(int n) {
			// IMPORTANT: Please reset any member data you declared, as
			// the same Solution instance will be reused for each test case.
			vector<string> s;
			fun(s, "", 0, n);
			return s;
		}

		void fun(vector<string> &s, string result, int stack, int left)
		{
			if(stack ==0 && left == 0)
			{
				s.push_back(result);
				return;
			}

			if(left > 0)
			{
				if(stack==0)
				{
					fun(s, result+'(', stack+1, left-1);
				}
				else
				{
					fun(s, result+'(', stack+1, left-1);
					fun(s, result+')', stack-1, left);
				}
			}
			else
			{
				if(stack>0)
				{
					fun(s, result+')', stack-1, left);
				}	
			}
		}
};

좋은 웹페이지 즐겨찾기