Generate Parentheses

Last updated Jul 26, 2023 Edit Source

• Programming
• Interviewprep
• Leetcode

Generate Parentheses es el problema de Leetcode numero 22. En este problema, se te instruye lo siguiente:

Dado n numero de parentesis validos (Es decir, n aperturas de parentesis y n cerraduras de parentesis) genera todas las combinaciones posibles validas. Por ejemplo si n = 3 entonecs las combinaciones serian: ["((()))","(()())","(())()","()(())","()()()"]

Para solucionar este problema necesitamos conocer las condiciones para generar una solucion valida de parentesis:

• Solo se puede obtener una solucion cuando el numero de parentesis de apertura y de cierre sea igual que el numero maximo permitido, es decir solo si x == y == n.
• Solo se puede seguir insertando parentesis de apertura si el numero de ellos (x) es menor que el maximo permitido (n), es decir solo si x < n.
• Solo se puede insertar un parentesis de cierre si el numero de ellos (y) es menor que el numero actual de parentesis de apertura (x), es decir solo si y < x.

Basada en estas tres condiciones podriamos aplicar una solucion que combine Recursividad y Backtracking.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

function generateParenthesis(n: number): string[] {
	const r: string[] = [];
	const s: string[] = [];

	function backtrack(open: number, closed: number) {
		if (open === closed && closed === n) {
			const valid = s.join("");
			r.push(valid);
			return;
		}

		if (open < n) {
			s.push("(");
			backtrack(open + 1, closed);
			s.pop();
		}

		if (closed < open) {
			s.push(")");
			backtrack(open, closed + 1);
			s.pop();
		}
	}

	backtrack(0, 0);
	return r;
}