Cadena aditiva |
Una cadena aditiva de n es una secuencia de enteros [a0, a1, a2, ..., am] con las siguientes cuatro propiedades:
Tenemos un entero n. Se pide construir una cadena aditiva para n de longitud mínima. Si hay más de una de tales cadenas, cualquiera de ellas será aceptable.
Por ejemplo, [1,2,3,5] y [1,2,4,5] son ambas soluciones válidas cuando se pide una cadena de aditiva para 5.
Sugerencia: El problema es un poco crítico en tiempo, así que usa las condiciones de poda adecuadas donde sea necesario para reducir el espacio de búsqueda.
5 7 12 15 77 0
1 2 4 5 1 2 4 6 7 1 2 4 8 12 1 2 4 5 10 15 1 2 4 8 9 17 34 68 77