Desafío Semanal #2: Generación de Paréntesis con Backtracking y Recursión

Continuo la serie semanal de retos de programación y en esta entrega rehago y traduzco al español el artículo sobre Generar Parentesis usando backtracking y recursión explicando el problema, la idea algorítmica y cómo implementarlo de forma clara y práctica

Resumen del problema Se recibe un entero n y hay que devolver todas las cadenas bien formadas de n pares de paréntesis. El objetivo es enumerar todas las combinaciones válidas de paréntesis garantizando equilibrio y orden correcto

Conceptos clave Backtracking y recursión Backtracking es una técnica para explorar sistemáticamente todas las configuraciones posibles mediante decisiones sucesivas, avanzar cuando una elección es prometedora y retroceder cuando no lo es. Es ideal para generar combinaciones con restricciones. La recursión modela naturalmente la construcción carácter a carácter de la solución, pasando el estado actual a llamadas más profundas hasta alcanzar una solución completa

Enfoque general y estados Seguimos dos contadores openN y closeN que representan cuántos paréntesis de apertura y cierre hemos usado hasta ahora. Restricciones fundamentales No podemos usar más de n paréntesis de apertura. Solo podemos añadir un paréntesis de cierre si hay al menos un paréntesis de apertura sin cerrar, es decir closeN debe ser menor que openN. Estas condiciones evitan prefijos inválidos

Estructura de la solución La solución se organiza en una función recursiva backtrack que mantiene un camino actual representado por un arreglo o pila de caracteres y un arreglo result donde acumulamos las cadenas completas. En cada llamada se comprueba si openN y closeN han alcanzado n y si es así se añade la cadena resultante. Si no, se bifurca: se intenta añadir un paréntesis de apertura si todavía quedan disponibles y se intenta añadir un paréntesis de cierre si eso mantiene la validez. Tras explorar cada rama se revierte la decisión para probar otras opciones, que es la esencia del backtracking

Pseudocódigo de alto nivel function generateParenthesis(n) crear resultado como arreglo vacío crear pila como arreglo vacío function backtrack(openN, closeN) if openN == n and closeN == n añadir a resultado la cadena construida a partir de la pila if openN < n añadir a la pila el caracter paréntesis apertura avanzar recursivamente con openN + 1 revertir la pila if closeN < openN añadir a la pila el caracter paréntesis cierre avanzar recursivamente con closeN + 1 revertir la pila llamar a backtrack con 0, 0 devolver resultado

Explicación paso a paso Estado y restricciones openN cuenta los paréntesis apertura usados closeN cuenta los paréntesis cierre usados Condiciones de validez openN no puede superar n closeN no puede superar openN durante la construcción

Elección de paréntesis apertura Si openN es menor que n podemos añadir otro paréntesis apertura, avanzar la recursión y luego quitar ese carácter para probar otras ramas

Elección de paréntesis cierre Solo añadimos un paréntesis cierre si closeN es menor que openN para mantener la cadena válida en cada prefijo

Construcción de resultados La recursión comienza en backtrack 0, 0 y cada vez que ambos contadores alcanzan n añadimos la cadena construida al resultado. No es necesaria una filtración posterior porque nunca construimos prefijos inválidos

Ejemplo con n = 3 Resultado esperado en alguna orden puede ser ((())), (()()), (())(), ()(()), ()()() Todas las cadenas están balanceadas y representan todas las combinaciones únicas de 3 pares

Aplicaciones prácticas y variantes Este patrón de recursión y backtracking se reutiliza en muchos problemas combinatorios como generar combinaciones, permutaciones, particiones y expresiones válidas que usan diferentes tipos de delimitadores. Una variante interesante es permitir varios tipos de delimitadores como corchetes y llaves simultáneamente o introducir prioridades entre tipos de delimitadores

Sobre la implementación en TypeScript La versión original usa arrays para el camino actual y mantiene contadores numéricos. En TypeScript se puede tipar claramente la función y las variables para mayor seguridad. El rendimiento es el típico de la enumeración combinatoria donde el número de soluciones crece de forma exponencial con n, pero las restricciones impuestas reducen significativamente las ramas inválidas exploradas

Q2BSTUDIO y cómo te podemos ayudar En Q2BSTUDIO somos una empresa de desarrollo de software y aplicaciones a medida especializada en soluciones tecnológicas modernas. Ofrecemos software a medida, aplicaciones a medida y proyectos personalizados que integran inteligencia artificial y ciberseguridad. Creamos soluciones que combinan servicios cloud aws y azure con servicios inteligencia de negocio y herramientas como power bi para transformar datos en decisiones accionables. Nuestras capacidades en inteligencia artificial incluyen desarrollo de agentes IA, soluciones de ia para empresas y sistemas de recomendación y automatización que potencian la productividad

Servicios destacados desarrollo de software a medida aplicaciones a medida integración de inteligencia artificial implementaciones de ciberseguridad servicios cloud aws y azure servicios inteligencia de negocio consultoría en ia para empresas desarrollo de agentes IA dashboards con power bi y analítica avanzada

Por qué elegirnos Q2BSTUDIO combina experiencia técnica y enfoque empresarial para entregar soluciones escalables y seguras. Diseñamos arquitecturas en la nube, garantizamos buenas prácticas de seguridad y aplicamos inteligencia de negocio para alinear tecnología con objetivos de negocio. Si buscas un partner para transformar una idea en un producto robusto y escalable, podemos ayudarte con desarrollo ágil, integración de modelos de inteligencia artificial y despliegues en servicios cloud aws y azure

Conclusión Generar paréntesis es un ejercicio didáctico que ilustra perfectamente cómo la recursión y el backtracking trabajan juntos: la recursión explora la estructura en árbol y el backtracking permite deshacer decisiones para probar otras combinaciones. Estas técnicas son fundamentales en problemas combinatorios y encuentra aplicación directa en soluciones reales que desarrollamos en Q2BSTUDIO como parte de proyectos de software a medida inteligencia artificial y ciberseguridad Si quieres que adaptemos este patrón a un caso concreto de tu empresa o que integremos una solución basada en IA contacta con Q2BSTUDIO para una consultoría inicial y un plan de trabajo enfocado en resultados

Enlaces útiles NeetCode problemas generate parentheses https://neetcode.io/problems/generate-parentheses?list=neetcode150 Repositorio con soluciones TypeScript https://github.com/TylerMutai/coding-challenges-solutions/tree/main/ts-coding-challenges-solutions