Código acm.uva.es: 529

  Cadena aditiva  

Una cadena aditiva de n es una secuencia de enteros [a₀, a₁, a₂, ..., a_m] con las siguientes cuatro propiedades:

• a₀ = 1
• a_m = n
• a₀<a₁<a₂<...<a_m-1<a_m
• Para cualquier k (1<= k <= m) existen dos enteros i y j (no necesariamente diferentes) (0<= i, j <= k-1) con a_k = a_i + a_j

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.

Entrada 

El fichero de entrada contendrá uno o más casos de prueba. Cada caso contiene un entero n (con 1 < n < 100). La entrada termina con un valor de 0 para n.

Salida 

Para cada caso de prueba, escribir una línea que contenga la secuencia de enteros requerida. Separar los números con un espacio en blanco.

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.

Ejemplo de entrada 

5
7
12
15
77
0

Ejemplo de salida 

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