Combination Sum

Q: ¿Por qué haces la llamada recursiva con i y no con i + 1 en Combination Sum?

Recurrir con i permite que el siguiente valor vuelva a ser el mismo candidato, que es como un valor se usa más de una vez. Recurrir con i + 1 avanza más allá de él, lo que convierte el problema en la variante en la que cada candidato se usa como máximo una vez. La otra mitad de la regla es igual de importante: nunca retroceder a un índice anterior a i mantiene todas las combinaciones en orden ascendente y evita los duplicados.

MedioBacktracking

+10

Se te da una lista candidates de distintos enteros positivos y un entero positivo target. Encuentra todas las combinaciones de candidatos cuyos valores sumen exactamente target, donde cada candidato puede usarse tantas veces como quieras. Dos combinaciones son iguales cuando usan los mismos valores la misma cantidad de veces, así que [2, 3, 3] y [3, 2, 3] cuentan como una sola.

Devuelve cada combinación con sus valores en orden ascendente y las combinaciones en orden lexicográfico: compara dos combinaciones valor por valor desde la izquierda, y la que tenga el valor más pequeño en la primera diferencia va primero.

Función

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: los distintos valores que puedes usar, en cualquier orden y tantas veces como quieras
targetinteger: el total de cada combinación debe alcanzar exactamente
Devuelveinteger-2d-array: cada combinación que suma el objetivo, cada una en orden ascendente, enumeradas en orden lexicográfico

Restricciones

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Todos los valores de candidates son diferentes y están en un orden cualquiera.
Al menos una combinación alcanza target, y como máximo 150 lo hacen.

Ejemplos

Entrada: candidates = [6, 2, 3]target = 8
Salida: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Explicación: Cuatro doses hacen 8, al igual que 2 + 3 + 3 y 2 + 6. Las tres opciones empiezan con 2, así que el segundo valor establece el orden: 2, después 3 y luego 6. Sin un 2, solo tienes 3 y 6, y cualquier combinación de estos es múltiplo de 3, que no es el caso de 8.

Entrada: candidates = [5, 3, 4]target = 11
Salida: [[3, 3, 5], [3, 4, 4]]
Explicación: 3 + 3 + 5 y 3 + 4 + 4 suman 11. Coinciden en el primer valor y, en el segundo, el 3 es menor que el 4, así que [3, 3, 5] va primero. Ninguna combinación de 4 y 5 únicamente suma 11.

Entrada: candidates = [4, 9]target = 9
Salida: [[9]]
Explicación: 9 por sí solo es una combinación. Los múltiplos de 4 solo dan 4, 8 y 12 al pasar por 9, y 4 + 9 ya es 13, así que [9] es la única respuesta.

+12 pruebas ocultas al enviar

Para ir más allá

Cada candidato ahora puede usarse como máximo una vez, y candidates puede contener valores repetidos. ¿Cómo cambias la búsqueda para que ninguna combinación aparezca dos veces?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Cada respuesta es un multiconjunto de candidatos, y la trampa está en construir el mismo multiconjunto más de una vez: elegir 2, después 3 y luego 3, y elegir 3, después 2 y luego 3, dan la misma combinación. La idea que lo resuelve es construir cada combinación en orden ascendente, de modo que solo haya una forma de construirla, y ordenar los candidatos para que una rama se detenga en cuanto el siguiente valor sea mayor que lo que queda. El mismo recorrido ascendente te da las combinaciones en orden lexicográfico sin necesidad de ordenarlas al final.

Prueba cada cantidad de cada candidato

Correcto, pero no termina con las pruebas más grandes

Intuición

Una combinación queda completamente descrita por la cantidad de copias que usa de cada candidato. Para [6, 2, 3] y el objetivo 8, la respuesta [2, 3, 3] es un 2, dos 3 y ningún 6. Así que una forma de encontrar todas las respuestas es probar todas las cantidades posibles de cada candidato y conservar las opciones cuyo total sea exactamente target. Un candidato c puede aparecer como máximo target / c veces, así que su cantidad va de 0 hasta ese límite.

Imagina un árbol de decisiones con un nivel por candidato, después de ordenarlos. En el nivel i decides cuántas copias del valor en la posición i debes tomar, y cada hoja del nivel inferior representa una elección completa de cantidades. Cada multiconjunto tiene exactamente una lista de cantidades, así que ninguna combinación se encuentra dos veces. Probar primero la cantidad más grande también da el orden requerido: cuando dos respuestas difieren por primera vez en la cantidad de algún valor, la que tiene más copias sigue teniendo ese valor pequeño donde la otra ya tiene uno mayor, así que aparece primero.

El problema es el tamaño del árbol. La cantidad de hojas es el producto de target / c + 1 para todos los candidatos: para [2, 3, 6] ordenado y el objetivo 8, eso da 5 × 3 × 2 = 30 hojas para 3 respuestas. Cada candidato mayor que target / 2 duplica la cantidad de hojas aunque pueda aparecer como máximo una vez, así que 40 candidatos de ese tipo por sí solos dan 2^40, aproximadamente 10^12, hojas. Las pruebas grandes están construidas de esa manera, y este enfoque no puede completarlas.

Algoritmo

Ordena los candidatos y crea un arreglo de cantidades, una por cada valor.
Escribe choose(i, total), que fija la cantidad del valor en el índice i.
Para k, desde target / nums[i] hasta 0, establece la cantidad en k y llama a choose(i + 1, total + k × nums[i]).
Cuando cada valor tenga una cantidad, conserva la combinación si total es igual a target, escribiendo cada valor tantas veces como indique su cantidad.
Llama a choose(0, 0). Las combinaciones conservadas ya están en orden lexicográfico.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Retrocede en orden ascendente y poda

Intuición

Construye cada combinación valor a valor, tal como la escribirías: en orden ascendente. El índice inicial impone ese orden. Después de colocar nums[i], el siguiente valor puede ser nums[i] de nuevo, porque un candidato puede repetirse, o cualquier valor posterior, pero nunca uno anterior. Por eso, la llamada que colocó el índice i recorre los valores desde i en adelante. Cada combinación tiene exactamente un orden ascendente, así que tiene exactamente un camino en el árbol y nunca se construye un duplicado como [3, 2, 3].

Este es el árbol completo para [2, 3, 6] ordenado y el objetivo 8. La raíz tiene 8 restantes y prueba 2, 3 y 6. Bajo 2 quedan 6. Bajo 2, 2 quedan 4, y 2, 2, 2 deja 2, que con un 2 más se convierte en la respuesta [2, 2, 2, 2]; 2, 2, 3 deja 1 y termina. Bajo 2, 3 quedan 3 y solo se pueden probar 3 y 6; el 3 da [2, 3, 3]. Bajo 2, 6 no queda nada: [2, 6]. Bajo 3 solo se pueden probar 3 y 6, y 3, 3 deja 2, que no completa la suma. Bajo 6 quedan 2 y solo se puede probar 6. Doce llamadas en total, frente a las 30 hojas del primer enfoque.

Ordenar convierte un callejón sin salida en una parada temprana. Cuando nums[i] es mayor que lo que queda, todos los valores posteriores también son mayores, así que sales del bucle con break en vez de probar el resto. En el árbol anterior, el nodo 2, 2, 3 con 1 restante examina 3, ve que no encaja y nunca examina 6. La búsqueda solo visita prefijos cuya suma sigue siendo como máximo target, por lo que las pruebas grandes que hacen fracasar el primer enfoque requieren aquí unos pocos miles de llamadas.

El orden de salida proviene del mismo recorrido. En cada nivel, el bucle prueba primero los valores más pequeños, y cada combinación se escribe en orden ascendente. Dos respuestas difieren por primera vez en el nivel donde sus caminos se separan, y el camino con el valor menor en ese nivel se exploró primero, así que las respuestas aparecen en orden lexicográfico. Una combinación nunca puede ser prefijo de otra, ya que los valores son positivos y ambas alcanzan el mismo total.

Algoritmo

Ordena los candidatos en orden ascendente.
Escribe backtrack(start, remaining) que comparta una lista path. Si remaining es 0, guarda una copia de path.
De lo contrario, recorre i desde start hasta el final. Si nums[i] > remaining, interrumpe el bucle: todos los valores posteriores son mayores.
Añade nums[i], llama a backtrack(i, remaining-nums[i]) con i, no con i + 1, para que el valor pueda repetirse, y luego elimínalo.
Llama a backtrack(0, target) y devuelve las combinaciones guardadas, ya en orden lexicográfico.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Errores comunes y casos límite

La mayoría de las respuestas incorrectas se deben a cómo se ordena la búsqueda, no a la aritmética.

Recorrer todos los candidatos en cada nivel, en lugar de empezar desde el índice actual, genera [2, 3, 3], [3, 2, 3] y [3, 3, 2] como tres respuestas. Ordenar cada respuesta y eliminar los duplicados después produce la lista correcta, pero requiere exponencialmente más trabajo.
Hacer la llamada recursiva con i + 1 en lugar de i hace que cada valor solo pueda aparecer una vez, por lo que falta [2, 2, 2, 2].
Guardar path en sí, en lugar de una copia: entonces todas las respuestas guardadas son la misma lista, que el retroceso ha vaciado al final.
Usar break con candidatos que no ordenaste. Con [6, 2, 3] y 2 pendientes, el bucle se detiene en 6 y nunca prueba el 2.
Devolver las combinaciones en el orden que sugiere la entrada sin ordenar. La lista esperada está en orden lexicográfico, que la búsqueda ordenada produce sin una ordenación adicional.
En Lua y R, los arreglos empiezan en 1, así que la primera llamada empieza en el índice 1 y el bucle llega hasta la longitud del arreglo.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de Combination Sum?

La búsqueda con retroceso es exponencial. Con n candidatos, un objetivo t y el candidato más pequeño m, una combinación contiene como máximo t/m valores y cada paso tiene como máximo n opciones, lo que acota el trabajo en O(n^(t/m)). La poda con candidatos ordenados mantiene el número real de llamadas muy por debajo de ese límite, porque la búsqueda solo visita prefijos cuya suma sigue siendo como máximo t. El espacio adicional es O(t/m) para la ruta actual y la pila de llamadas, además de la salida.

¿Por qué haces la llamada recursiva con i y no con i + 1 en Combination Sum?

Recurrir con i permite que el siguiente valor vuelva a ser el mismo candidato, que es como un valor se usa más de una vez. Recurrir con i + 1 avanza más allá de él, lo que convierte el problema en la variante en la que cada candidato se usa como máximo una vez. La otra mitad de la regla es igual de importante: nunca retroceder a un índice anterior a i mantiene todas las combinaciones en orden ascendente y evita los duplicados.

¿Cómo evitas las combinaciones duplicadas sin un conjunto?

Genera todas las combinaciones en un orden fijo y ascendente. El índice inicial lo garantiza: después de colocar nums[i], la búsqueda solo examina nums[i] y los valores posteriores. Así, cada combinación tiene exactamente un recorrido en el árbol de búsqueda, por lo que se genera una sola vez y no se necesita ningún conjunto ni una deduplicación final.

¿Se puede resolver Combination Sum mediante programación dinámica?

Sí. Mantén, para cada total de 0 al objetivo, la lista de combinaciones que lo alcanzan, y añade un candidato a la vez para que los valores de cada lista sigan en orden ascendente, la misma idea que contar las formas de dar cambio. Nunca explora dos veces un callejón sin salida, pero almacena cada combinación parcial para cada total, lo que requiere mucha más memoria que la búsqueda con retroceso, y puede que haya que ordenar la lista final. Como la salida en sí puede ser exponencial, la búsqueda con retroceso suele ser la respuesta habitual.

Python

def combinationSum(candidates, target):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

candidates = [6, 2, 3]
target = 8

Esperado

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]