Considere el conjunto: {1,2,5,6,8} y la suma para encontrar es 9.
Para formar subconjuntos, puede considerar un elemento o no considerarlo. Por lo tanto, hay 2 formas en cada elemento para formar subconjuntos. Esto da 2 * 2 * 2 * … 2 = 2 ^ n subconjuntos. El método de búsqueda exhaustivo calcula todos los subconjuntos de un conjunto y verifica cuál de esos suma a la suma dada.
Retroceder es una optimización sobre este método. Llamemos al conjunto como “input”, una matriz de enteros.
1. Comience construyendo un árbol con el valor raíz como 0.
2. Ramifíquese hacia la izquierda para indicar “sin entrada [0]” y hacia la derecha para indicar “sin entrada [0]”. Para nuestro ejemplo, la rama izquierda estará con 1 y la rama derecha estará sin 1.
3. Haga el valor del nodo izquierdo como la suma del valor del padre y el valor de la rama, que es 0 + 1 = 1 para el hijo izquierdo y 0 + 0 = 0 para el hijo derecho.
4. Ahora, construye recursivamente el árbol. Desde el primer hijo izquierdo, bifurque hacia la izquierda y hacia la derecha para indicar con y sin entrada [1] respectivamente., De modo que sus hijos tendrán valores 1 + 2 = 3 y 1 + 0 = 1.
De esta manera, seguimos construyendo el árbol hasta que ocurra una de las dos cosas:
1. La suma resultante del valor del nodo padre + el valor de la rama es igual a nuestra suma dada 9. Por ejemplo, la secuencia de considerar el primer elemento (1), el segundo elemento (2), sin considerar el tercer elemento (5), considerando el cuarto elemento (5) dará 1 + 2 + 6 = 9. Cuando llegamos a la suma dada, dejamos de ramificar / generar nodos hijos y devolvemos el camino que atravesamos, que es 1-> 2-> 6.
2. La suma resultante es más que la suma dada. Por ejemplo, cuando considera 1, 2, 5, no es necesario ramificarse desde aquí con 6 porque (1 + 2 + 5) + 6> 9 (suma dada).
- ¿Cuáles son algunas habilidades de programación, algoritmos o marcos que se ven muy bien pero que son muy simples?
- ¿Cuáles son algunos buenos libros para aprender y practicar estructuras de datos y algoritmos?
- ¿Hay algo en el universo que no sea algorítmico?
- ¿Con qué tipo de algoritmo debo comenzar desde el principio?
- Cómo implementar la implementación de la pila y la cola en las estructuras de datos
Entonces, en lugar de verificar todos los subconjuntos, calculamos el árbol en función de las restricciones anteriores.
