首页 > 代码库 > 回溯法输出n对括号的合法组合
回溯法输出n对括号的合法组合
排列组合这种问题似乎用回溯法比较合适，括号只有左括号和或右扣号，把左扣号定好了，右括号也就定好了。
用一个栈来存中间结果，优先放左扣号，符合条件输出后回溯。
#include <stdio.h>int main(int argc, char *argv[]) { int n = atoi(argv[1]); char s[10000]; int si = -1; //未放入栈的左括号数 int left_count = n; int i = 0; while (1) { if (left_count > 0) { //左括号还没放完，继续放 s[++si] = ‘(‘; --left_count; continue; } //左括号已经放完了，可以输出了 for (i = 0; i <= si; i++) { printf("%c", s[i]); } for (i = si + 1; i < n * 2; i++) { printf(")", s[i]); } printf("\n"); //开始回溯, 直到能将某一个左扣号变成右扣号 while (si >= 0) { if (s[si] == ‘(‘) { //s[0]到s[si-1]中，左括号数超过一半，才能将s[si]变成左扣号 if ((n - left_count - 1) * 2 > si) { s[si] = ‘)‘; left_count++; break; } left_count++; } si--; } if (si < 0) { //回溯不到了 break; } }}
输出结果：
lishuai@local$ ./a.out 1
()
lishuai@local$ ./a.out 2
(())
()()
lishuai@local$ ./a.out 3
((()))
(()())
(())()
()(())
()()()
lishuai@local$
./a.out 1
()
./a.out 2
(())
()()
./a.out 3
((()))
(()())
(())()
()(())
()()()
回溯法输出n对括号的合法组合
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。