El problema Restore IP Addresses consiste en tomar una cadena de números y colocar puntos en las posiciones correctas para generar todas las direcciones IP válidas posibles. La clave está en aplicar backtracking y dividir el reto en subproblemas pequeños, como validar cada grupo de dígitos antes de seguir explorando. Si te interesan los algoritmos de búsqueda con poda, esta solución en C++ te muestra cómo pensar el problema paso a paso.

¿Qué define una dirección IP válida en este problema?

Antes de escribir código, necesitas saber qué cuenta como un número válido dentro de una IP. Una IP tiene cuatro grupos separados por puntos, y cada grupo debe cumplir reglas específicas.

• Cada grupo debe estar entre 0 y 255.
• No puede tener ceros a la izquierda, salvo que el grupo sea exactamente 0.
• Cada grupo tiene entre 1 y 3 dígitos.

¿Qué es un número válido en una IP? Es un valor entre 0 y 255, sin ceros a la izquierda cuando tiene más de un dígito. Por ejemplo, 0 sí vale, pero 01 no.

Esta validación se convierte en una función aparte llamada esValido, que recibe un string con el grupo y devuelve true o false [03:45].

¿Por qué usar backtracking para generar las IPs?

La idea del backtracking es construir una solución parcial e ir descartando caminos en cuanto detectas que no llevan a una respuesta válida. En lugar de probar todas las combinaciones posibles de puntos, podas ramas completas apenas un grupo deja de cumplir las reglas [01:30].

La lógica recursiva funciona así:

1. Recorres la cadena moviendo un índice que marca el inicio del grupo actual.
2. Pruebas grupos de 1, 2 o 3 caracteres.
3. Si el grupo es válido, agregas un punto y llamas la función con el siguiente índice.
4. Si ya formaste cuatro grupos y consumiste toda la cadena, guardas la IP en el resultado.

¿Cómo se estructura la función recursiva?

La función crearCombinaciones recibe la cadena original, el vector de IPs válidas, el índice actual, la cantidad de grupos formados y la IP que vas construyendo [05:20].

cpp void crearCombinaciones( const string& IP, vector<string>& IPsValidas, int index, int cantidadNumeros, string IPValida ) { if (cantidadNumeros > 4) return; if (cantidadNumeros == 4 && index == IP.length()) { IPsValidas.push_back(IPValida); return; } for (int i = 1; i < 4; i++) { if (index + i > IP.length()) break; string numero = IP.substr(index, i); if (!esValido(numero)) continue; string IPConPuntoNuevo = IPValida + numero + (cantidadNumeros == 3 ? "" : "."); crearCombinaciones(IP, IPsValidas, index + i, cantidadNumeros + 1, IPConPuntoNuevo); } }

El bucle va de i = 1 a i < 4 porque ningún grupo válido tiene más de tres dígitos. Si el número con cuatro caracteres ya superaría 255, no tiene sentido evaluarlo [09:40].

¿Cómo se programa la validación de cada grupo?

La función esValido aplica tres reglas en orden y devuelve un boolean. Es corta, pero concentra toda la lógica de las restricciones de una IP.

cpp bool esValido(const string& numero) { if (numero.length() == 0) return false; if (numero.length() > 1 && numero[0] == '0') return false; return stoi(numero) >= 0 && stoi(numero) <= 255; }

¿Por qué se descartan los ceros a la izquierda? Porque una IP como 192.01.1.1 no es válida. Solo 0 por sí solo es aceptado como grupo, no 01 ni 001.

¿Qué hace la función principal restoreIpAddresses?

La función que se llama desde fuera solo inicializa el vector de resultados y dispara la recursión [04:50].

cpp vector<string> restoreIpAddresses(string s) { vector<string> IPsValidas; crearCombinaciones(s, IPsValidas, 0, 0, ""); return IPsValidas; }

El índice arranca en 0, no hay grupos formados todavía y la IP en construcción está vacía. A partir de ahí, la recursión se encarga de explorar y podar.

¿Qué tienen en común este problema y N reinas?

Ambos problemas se resuelven con la misma estructura mental: construyes una solución parcial, validas en cada paso si sigue teniendo sentido y, si no, retrocedes. En N reinas colocas reinas en un tablero sin que se ataquen; aquí colocas puntos sin romper las reglas de una IP. La poda temprana es lo que hace eficiente al backtracking en ambos casos.

Te dejo el reto: implementa N reinas, compara tu código con esta solución y cuéntame en los comentarios qué patrones encontraste en común.