首页 > 代码库 > 输出括号所有合法匹配
输出括号所有合法匹配
原文链接:http://blog.csdn.net/doc_sgl/article/details/8917476
简答题最后一题，编程实现所有括号的合法匹配
如输入3
输出："((()))”, “(()())”, “(())()”, “()(())”, “()()()”
思路：深搜+剪枝，关键在于记录已经用掉的左括号个数和右括号的个数，
1，当用过的左括号个数小于右括号则非法；
2，当二者个数和大于2N则非法；
3，当二者个数相等且数目等于2N此时输出。
#include <iostream>using namespace std;void DFS_bracket(char* str,int n, int left_used, int right_used){ if(left_used == right_used && left_used + right_used == 2*n) { for(int i = 0; i < left_used*2; ++i) cout<<str[i]; cout<<endl; return; } if(left_used < right_used || left_used + right_used >= 2*n) { return ; } int index = left_used + right_used; str[index] = ‘(‘; DFS_bracket(str, n, left_used + 1, right_used); str[index] = ‘)‘; DFS_bracket(str, n, left_used, right_used + 1);}int main(){ int parenthesisnum; cin>>parenthesisnum; char* str = new char[parenthesisnum*2+1]; DFS_bracket(str,parenthesisnum,0,0); return 0;}
输出括号所有合法匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。