package genparen

func iter(result *[]string, current string, left int, right int) {
	if left == 0 && right == 0 {
		*result = append(*result, current)
		return
	}

	if left > 0 {
		iter(result, current+"(", left-1, right)
	}
	if right > left {
		iter(result, current+")", left, right-1)
	}
}

func generateParenthesis(n int) []string {
	result := make([]string, 0, n^2)
	iter(&result, "", n, n)
	return result
}

func Gen(n int) []string {
	return generateParenthesis(n)
}