#include <unistd.h>
#include <stdlib.h>

typedef struct s_result
{
	char				*str;
	struct s_result		*next;
}	t_result;

int	ft_strlen(char *str)
{
	int	len;

	len = 0;
	while (str[len])
		len++;
	return (len);
}

int	ft_strcmp(char *s1, char *s2)
{
	int	i;

	i = 0;
	while (s1[i] && s2[i] && s1[i] == s2[i])
		i++;
	return (s1[i] - s2[i]);
}

char	*ft_strdup(char *src)
{
	char	*dup;
	int		len;
	int		i;

	len = ft_strlen(src);
	dup = malloc(len + 1);
	if (!dup)
		return (NULL);
	i = 0;
	while (i < len)
	{
		dup[i] = src[i];
		i++;
	}
	dup[len] = '\0';
	return (dup);
}

void	add_result(t_result **results, char *str)
{
	t_result	*new;
	t_result	*current;

	current = *results;
	while (current)
	{
		if (ft_strcmp(current->str, str) == 0)
			return ;
		current = current->next;
	}
	new = malloc(sizeof(t_result));
	if (!new)
		return ;
	new->str = ft_strdup(str);
	if (!new->str)
	{
		free(new);
		return ;
	}
	new->next = *results;
	*results = new;
}

void	print_results(t_result *results)
{
	t_result	*current;
	int			i;

	current = results;
	while (current)
	{
		i = 0;
		while (current->str[i])
		{
			write(1, &current->str[i], 1);
			i++;
		}
		write(1, "\n", 1);
		current = current->next;
	}
}

void	free_results(t_result *results)
{
	t_result	*temp;

	while (results)
	{
		temp = results;
		results = results->next;
		free(temp->str);
		free(temp);
	}
}

void	solve(char *s, int pos, int left_rem, int right_rem, int open, char *path, t_result **results)
{
	int	len;

	len = ft_strlen(s);
	if (pos == len)
	{
		if (left_rem == 0 && right_rem == 0 && open == 0)
			add_result(results, path);
		return ;
	}
	if (s[pos] == '(' && left_rem > 0)
	{
		path[pos] = ' ';
		solve(s, pos + 1, left_rem - 1, right_rem, open, path, results);
	}
	if (s[pos] == ')' && right_rem > 0)
	{
		path[pos] = ' ';
		solve(s, pos + 1, left_rem, right_rem - 1, open, path, results);
	}
	path[pos] = s[pos];
	if (s[pos] == '(')
		solve(s, pos + 1, left_rem, right_rem, open + 1, path, results);
	else if (s[pos] == ')' && open > 0)
		solve(s, pos + 1, left_rem, right_rem, open - 1, path, results);
	else
		solve(s, pos + 1, left_rem, right_rem, open, path, results);
}

void	remove_invalid_parentheses(char *s)
{
	int			left_rem;
	int			right_rem;
	int			len;
	char		*path;
	int			i;
	t_result	*results;

	left_rem = 0;
	right_rem = 0;
	len = ft_strlen(s);
	results = NULL;
	i = 0;
	while (s[i])
	{
		if (s[i] == '(')
			left_rem++;
		else if (s[i] == ')')
		{
			if (left_rem > 0)
				left_rem--;
			else
				right_rem++;
		}
		i++;
	}
	path = malloc(len + 1);
	if (!path)
		return ;
	path[len] = '\0';
	solve(s, 0, left_rem, right_rem, 0, path, &results);
	print_results(results);
	free_results(results);
	free(path);
}

int	main(int argc, char **argv)
{
	if (argc != 2)
		return (1);
	remove_invalid_parentheses(argv[1]);
	return (0);
}