La solución recursiva a esto es extremadamente fácil.
- Si la lista de números está vacía, la respuesta es una lista con solo 0.
- Si la lista tiene dos o más elementos, divídalos en una cabeza (el primer elemento) y una cola (el resto de la lista). Encuentre todas las sumas posibles en la cola, duplique el resultado, agregue el encabezado a una de las copias y vuelva a fusionarlas en una sola lista, eliminando valores duplicados.
De acuerdo, C no es realmente el lenguaje que usaría para implementar esto.
Una ilustración de cómo funciona:
- ¿Qué estructura de datos es mejor para implementar una guía telefónica: Trie o Hash? ¿Por qué?
- ¿Podemos construir un sistema utilizando algoritmos de aprendizaje automático que puedan reemplazar a todas las empresas de consultoría financiera y técnica del mundo?
- ¿Cómo verificamos la corrección de un algoritmo?
- Conozco estructuras de datos y algoritmos. ¿Cómo programo un compilador simple?
- ¿Cuál es el mejor algoritmo para encontrar dos elementos iguales en una matriz?
sumas [1, 2, 3]
1 -> sumas [2, 3]
1 -> (2 -> sumas [3])
1 -> (2 -> (3 -> sumas []))
1 -> (2 -> (3 -> [0]))
1 -> (2 -> ([0], [3]))
1 -> (2 -> [0, 3])
1 -> ([0, 3], [2, 5])
1 -> [0, 2, 3, 5]
[0, 2, 3, 5], [1, 3, 4, 6]
[0, 1, 2, 3, 4, 5, 6]
Como otros ya han señalado correctamente, la memoria requerida solo para almacenar la respuesta es, en el peor de los casos, proporcional a [matemáticas] 2 ^ n [/ matemáticas], y así será el tiempo de ejecución.
También podría generar enteros de 0 a [matemática] 2 ^ n-1 [/ matemática] y usarlos como máscaras de bits para los elementos que se deben sumar. La peor eficiencia del caso es la misma, pero el caso promedio para el algoritmo recursivo es un poquito mejor.
