Introducción

El algoritmo de suma combinada (también llamado subset‑sum combinatorial) es una técnica para encontrar todas las combinaciones de elementos de una lista que, al sumarse, alcanzan un valor objetivo. Se utiliza en planificación, finanzas, optimización de recursos y, por supuesto, en entrevistas técnicas.

En este artículo profundizamos en su lógica, presentamos una implementación robusta en Python, comparamos su rendimiento con alternativas y ofrecemos buenas prácticas y trucos de troubleshooting.

Concepto básico

Dados:

• arr: lista de números enteros (pueden ser positivos, negativos o cero).
• target: entero que representa la suma deseada.

El objetivo es generar todas las combinaciones (subconjuntos) de arr cuya suma sea exactamente target. La solución típica recurre a una búsqueda recursiva con poda (pruning) para evitar explorar ramas imposibles.

Algoritmo paso a paso

1. Ordenar la lista (opcional, pero ayuda a podar más rápido).
2. Iniciar una búsqueda recursiva que mantenga:
   • Índice actual i en la lista.
   • Suma acumulada current_sum.
   • Conjunto parcial path que representa la combinación actual.
3. En cada llamada:
   • Si current_sum == target → guardar path como solución.
   • Si current_sum > target o i == len(arr) → retroceder (poda).
   • Explorar dos ramas:
     1. Incluir arr[i] y avanzar a i+1.
     2. Excluir arr[i] y avanzar a i+1.

Implementación en Python

A continuación se muestra una versión clara, con anotaciones de tipos y gestión de errores.

from typing import List
def suma_combinada(arr: List[int], target: int) -> List[List[int]]:
    """Devuelve todas las combinaciones de arr cuya suma sea target.
    Parámetros:
        arr (List[int]): lista de números (pueden ser negativos).
        target (int): suma deseada.
    Retorna:
        List[List[int]]: lista de soluciones; cada solución es una lista de enteros.
    """
    # Ordenamos para que la poda sea más eficaz.
    arr.sort()
    resultados: List[List[int]] = []
    def backtrack(i: int, current_sum: int, path: List[int]) -> None:
        # Caso base: encontramos una solución válida.
        if current_sum == target:
            resultados.append(path.copy())
            return
        # Si superamos el objetivo o agotamos la lista, terminamos esta rama.
        if i == len(arr) or current_sum > target:
            return
        # --- Opción 1: incluir arr[i] ---
        path.append(arr[i])
        backtrack(i + 1, current_sum + arr[i], path)
        path.pop()  # backtrack
        # --- Opción 2: excluir arr[i] ---
        # Saltamos valores duplicados para evitar combinaciones redundantes.
        while i + 1 < len(arr) and arr[i] == arr[i + 1]:
            i += 1
        backtrack(i + 1, current_sum, path)
    backtrack(0, 0, [])
    return resultados
# Ejemplo de uso
if __name__ == "__main__":
    datos = [3, 34, 4, 12, 5, 2]
    objetivo = 9
    print("Combinaciones que suman", objetivo, ":")
    for combo in suma_combinada(datos, objetivo):
        print(combo)

Salida esperada:

Combinaciones que suman 9 :
[3, 4, 2]
[4, 5]
[3, 2, 4]

La función maneja duplicados y evita combinaciones repetidas gracias al while que salta valores idénticos.

Comparativa con técnicas alternativas

Casos de uso del mundo real

• Finanzas: encontrar combinaciones de transacciones que expliquen una discrepancia en el balance.
• Logística: cargar contenedores con pesos exactos para maximizar la utilización del espacio.
• Juegos: determinar combinaciones de cartas o fichas que sumen un valor objetivo.
• Data Science: generar subconjuntos de características que cumplan una restricción de coste.

Optimización y buenas prácticas

Poda temprana

Ordenar la lista y detener la recursión cuando current_sum + arr[i] > target evita miles de llamadas innecesarias.

Memoización

En escenarios donde se repiten sub‑problemas (por ejemplo, con muchos valores repetidos), almacenar (i, current_sum) en un dict reduce la complejidad a O(n·target) sin perder la capacidad de enumerar soluciones.

Uso de generadores

Convertir la función en un yield permite procesar resultados en streaming, lo que es útil cuando el número de combinaciones es muy grande.

def suma_combinada_gen(arr: List[int], target: int):
    arr.sort()
    def backtrack(i, current_sum, path):
        if current_sum == target:
            yield list(path)
            return
        if i == len(arr) or current_sum > target:
            return
        path.append(arr[i])
        yield from backtrack(i+1, current_sum+arr[i], path)
        path.pop()
        while i+1 < len(arr) and arr[i] == arr[i+1]:
            i += 1
        yield from backtrack(i+1, current_sum, path)
    yield from backtrack(0,0,[])

Troubleshooting frecuente

• Recursión demasiado profunda: para n > 1000 Python lanza RecursionError. Solución: usar un enfoque iterativo con pila explícita o incrementar sys.setrecursionlimit con cautela.
• Duplicados en la salida: ocurre si no se salta valores idénticos al excluir un elemento. El bucle while arr[i] == arr[i+1] evita esta situación.
• Rendimiento bajo con números negativos: la poda basada en current_sum > target ya no es válida. En esos casos, usar DP o limitar el rango de búsqueda mediante heurísticas.

Compatibilidad, rendimiento y escalabilidad

El algoritmo funciona en cualquier versión de Python ≥ 3.6. En entornos de producción donde la latencia es crítica, es recomendable:

• Compilar con Cython para obtener un speed‑up de 3‑5×.
• Desplegar en contenedores ligeros (Docker o Podman) con recursos limitados a evitar sobrecarga de memoria.
• Escalar horizontalmente usando celery o Ray para distribuir la búsqueda entre varios workers cuando n es grande.

Conclusión

El algoritmo de suma combinada es una herramienta versátil para problemas de combinación exacta. Con una implementación cuidadosa, poda inteligente y técnicas de memoización, puede resolver casos reales de forma eficiente, manteniendo la claridad del código y la capacidad de generar todas las soluciones posibles.