UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Entrega: 16 de febrero de 2006 a las 10pm

Diseñe un algoritmo usando la técnica de búsqueda con retroceso para resolver el siguiente problema: Dado un número natural N, encuentre todas las formas en las que se puede escribir como suma de números naturales distintos. Considere que dos formas son idénticas si sólo difieren en el orden de los sumandos. Por ejemplo, para N = 6 existen cuatro formas que son 1+2+3, 1+5, 2+4 y 6 (observe que una suma puede tener uno o más sumandos y también que 1+5 es lo mismo que 5+1 por lo que no se debe contar dos veces). Escriba un programa basado en su algoritmo que acepte como entrada un entero positivo N y que escriba como salida la cantidad de formas en las que se puede realizar la suma. De nuevo, para N = 6 la salida debe ser 4. Diga cuales son las respuestas obtenidas por su programa para toda N <= 10. ¿Cuál es el valor de N más grande que puede resolver en un minuto? ¿Y en una hora?