Combination Sum

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

La búsqueda con retroceso es exponencial. Con n candidatos, el objetivo t y el candidato más pequeño m , una combinación contiene como máximo t/m valores, con como máximo n opciones cada uno: O(n^(t/m)) . El espacio adicional es O(t/m) para la ruta y la pila de llamadas, además de la salida.

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, así es como se utiliza un valor más de una vez. Recurrir con i + 1 lo deja atrás, por lo que cada candidato podría utilizarse como máximo una vez.

Q: ¿Se puede resolver Combination Sum con programación dinámica?

Sí. Para cada total de 0 a target , conserva las combinaciones que lo alcanzan, añadiendo un candidato a la vez para que cada lista siga en orden ascendente. Nunca explora dos veces un callejón sin salida, pero almacena cada combinación parcial para cada total, lo que consume mucha más memoria. Como la salida en sí puede ser exponencial, el retroceso suele ser la solución.

MedioBacktracking

+10

Tienes una lista candidates de distintos enteros positivos y un entero positivo target. Encuentra todas las combinaciones de candidatos cuya suma sea exactamente target, usando cada candidato tantas veces como quieras. [2, 3, 3] y [3, 2, 3] son la misma combinación.

Devuelve cada combinación en orden ascendente y las combinaciones en orden lexicográfico: en la primera posición donde dos combinaciones difieren, va primero la que tiene el valor menor.

Función

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

candidatesinteger-array: los diferentes valores que puedes usar, en cualquier orden y tantas veces como quieras
targetinteger: el total que debe alcanzar exactamente cada combinación
Devuelveinteger-2d-array: todas las combinaciones que suman 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, sin ningún orden en particular.
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 2, 2 + 3 + 3 y 2 + 6 dan 8, ordenados por su segundo valor. Sin un 2, solo quedan 3 y 6, y sus sumas son múltiplos de 3, cosa que 8 no es.

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, y [3, 3, 5] va primero porque su segundo valor, 3, es menor que 4. Ninguna combinación de 4 y 5 suma 11.

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

La trampa consiste en construir dos veces la misma combinación: 2, 3, 3 y 3, 2, 3 son una sola respuesta. Construye cada combinación en orden ascendente para que tenga exactamente un camino, y ordena los candidatos para que una rama se detenga en cuanto el siguiente valor sea mayor que lo que queda.

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 cuántas copias de cada candidato utiliza: [2, 3, 3] es un 2, dos 3 y ningún 6. Prueba cada cantidad para cada candidato ordenado, desde target / c hasta 0, y conserva las opciones cuya suma sea exactamente target. Cada combinación tiene una única lista de cantidades, así que ninguna se encuentra dos veces. Empezar por las cantidades mayores da un orden lexicográfico: cuando dos respuestas difieren por primera vez, la que tiene más copias de un valor todavía contiene ese valor, mientras que la otra contiene uno mayor.

Para [2, 3, 6] y el objetivo 8, hay 5 × 3 × 2 = 30 hojas para 3 respuestas. Cada candidato mayor que target / 2 duplica las hojas, así que 40 candidatos de este tipo dan 2^40, aproximadamente 10^12.

Algoritmo

Ordena los candidatos y conserva un recuento por valor.
En choose(i, total), prueba cada recuento k desde target / nums[i] hasta 0 y llama a choose(i + 1, total + k × nums[i]).
Una vez que cada valor tenga un recuento, conserva la combinación si total es igual a target y escríbela a partir de los recuentos.
Llama a choose(0, 0).

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

Después de colocar nums[i], el siguiente valor puede ser otra vez nums[i] o cualquier valor posterior, nunca uno anterior. Una combinación tiene exactamente un orden ascendente, así que tiene exactamente un camino, y nunca se construye [3, 2, 3].

Para [2, 3, 6] ordenado y el objetivo 8, los caminos 2, 2, 2, 2 y 2, 3, 3 y 2, 6 llegan a 8. El camino 2, 2, 3 deja 1 y se detiene sin buscar 6, y 3, 3 deja 2, que no puede encajar con ningún valor. Eso supone 12 llamadas frente a las 30 hojas del conteo.

En cada nivel, el bucle prueba primero los valores más pequeños, así que las respuestas llegan en orden lexicográfico. Ninguna respuesta es prefijo de otra, ya que los valores son positivos y ambas alcanzan el mismo total.

Algoritmo

Ordena los candidatos.
En backtrack(start, remaining), guarda una copia de path, que se comparte, cuando remaining sea 0.
De lo contrario, recorre i desde start. Si nums[i] > remaining, termina el bucle: todos los valores posteriores son mayores.
Añade nums[i], llama a backtrack(i, remaining - nums[i]) y después elimínalo.
Llama a backtrack(0, target) y devuelve las combinaciones guardadas.

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

Recorrer todos los candidatos en cada nivel, en lugar de empezar desde el índice actual. [2, 3, 3], [3, 2, 3] y [3, 3, 2] después se cuentan como tres respuestas.
Hacer la recursión con i + 1 en lugar de i. Así, cada valor puede aparecer una sola vez, por lo que [2, 2, 2, 2] no aparece.
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 por completar, el bucle se detiene en 6 y nunca prueba el 2.

Preguntas frecuentes3

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

La búsqueda con retroceso es exponencial. Con n candidatos, el objetivo t y el candidato más pequeño m, una combinación contiene como máximo t/m valores, con como máximo n opciones cada uno: O(n^(t/m)). El espacio adicional es O(t/m) para la ruta 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, así es como se utiliza un valor más de una vez. Recurrir con i + 1 lo deja atrás, por lo que cada candidato podría utilizarse como máximo una vez.

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

Sí. Para cada total de 0 a target, conserva las combinaciones que lo alcanzan, añadiendo un candidato a la vez para que cada lista siga en orden ascendente. Nunca explora dos veces un callejón sin salida, pero almacena cada combinación parcial para cada total, lo que consume mucha más memoria. Como la salida en sí puede ser exponencial, el retroceso suele ser la solución.

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

Prueba #1

Prueba #2

Prueba #3

Argumentos

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

Salida Esperada

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