leetcode 22. Generate Parentheses
一、问题描述
给定n对括号，编写一个函数来生成正确括号的所有组合。例如，给定n = 3，解决方案集合为：[ "((()))", "(()())", "(())()", "()(())", "()()()"]
二、解题思路
要求生成所有组合并输出，考虑用递归记录，递归执行条件为：1）先放左括号 -- 当前左括号数<n，则放置左括号
2）后放右括号 -- 当前左括号数>当前右括号数，则放置右括号
三、解题算法
/****************************************************
Author:tmw
date:2018-5-16
****************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 500
int count = 0;//所有满足条件的组合情况个数
/**
参数说明：
ch ：当前放置的字符'('或')'
left_ch_count ：字符'('已放置的个数
right_ch_count ：字符')'已放置的个数
**final_r ：所有满足条件的组合情况
**/
/**将字符ch追加到原字符串串尾**/
char* add_one_ch( char* str, char ch )
{
str[strlen(str)] = ch;
str[strlen(str)+1] = '\0';
return str;
}
void dfs( int n, char* mid_result, int left_ch_count, int right_ch_count, char** final_r )
{
//终止条件
if( left_ch_count == n )
{
int i;
if( right_ch_count < n ) //右括号补齐
for(i=0; i<n-right_ch_count; i++)
add_one_ch(mid_result,')');
printf("mid_result = %s\n",mid_result);
strcpy(final_r[count],mid_result);
count++;
/**回退到补齐前的状态**/
mid_result[left_ch_count+right_ch_count]='\0';
return;
}
//先放左括号 -- 当前左括号数<n，则放置左括号
int mark_len1 = strlen(mid_result); //dfs前的状态
dfs(n,add_one_ch(mid_result,'('),left_ch_count+1,right_ch_count,final_r);
mid_result[mark_len1]='\0'; //状态恢复
//后放右括号 -- 当前左括号数>当前右括号数，则放置右括号
if( left_ch_count > right_ch_count )
{
int mark_len2 = strlen(mid_result);//dfs前的状态
dfs(n,add_one_ch(mid_result,')'),left_ch_count,right_ch_count+1,final_r);
mid_result[mark_len2]='\0';//状态恢复
}
}
char** generateParenthesis(int n, int* returnSize)
{
//初始化入参
int i;
char** final_r = (char**)malloc(MAX_SIZE*sizeof(char*));//最终结果返回数组
for( i=0; i<MAX_SIZE; i++ )
final_r[i] = (char*)malloc(MAX_SIZE*sizeof(char));
/**中间结果数组**/
char* mid_result = (char*)malloc(MAX_SIZE*sizeof(char));
strcpy(mid_result,"");
count = 0; //全局变量每次测试清0
dfs(n,mid_result,0,0,final_r);
*returnSize = count;
printf("count=%d\n");
return final_r;
}
梦想还是要有的，万一实现了呢~~~ ヾ(◍°∇°◍)ﾉﾞ~~~~
