[LeetCode] 0040. Suma combinada II

Explore diversas soluciones LeetCode en Python, C++, JavaScript, SQL y TypeScript. Ideal para preparación de entrevistas, aprendizaje y práctica de código en múltiples lenguajes de programación. Enlace de repositorio de Github

Tabla de contenido

Medio

Dada una colección de números candidatos (candidatos) y un número objetivo (objetivo), encuentra todas las combinaciones únicas en candidatos donde los números candidatos suman objetivo.

Cada número en candidatos sólo se puede utilizar una vez en la combinación.

Nota: El conjunto de soluciones no debe contener combinaciones duplicadas.

Ejemplo 1:

Aporte: candidatos = [10,1,2,7,6,1,5], objetivo = 8
Producción: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Ejemplo 2:

Aporte: candidatos = [2,5,2,1,2], objetivo = 5
Producción: 
[
[1,2,2],
[5]
]

Restricciones:

1 <= candidatos.longitud <= 100
1 <= candidatos[i] <= 50
1 <= objetivo <= 30

Pitón

				
					Complejidad de tiempo de #: O(2^n) Complejidad de espacio de #: O(n) al escribir clase de lista de importación Solución: def combinaciónSum2(self, candidatos: Lista[int], destino: int) -> Lista[Lista[int]] : respuesta = [] candidatos.sort() self.backtrack(candidatos, objetivo, 0, [], respuesta) return respuesta def backtrack(self, candidatos, objetivo: int, totalIdx: int, ruta: Lista[int], respuesta : Lista[int]): si objetivo < 0: devolver si objetivo == 0: respuesta.append(ruta) devolver para i en rango(totalIdx, len(candidatos)): si i > totalIdx y candidatos[i] == candidatos[i - 1]: continuar self.backtrack( candidatos, objetivo - candidatos[i], i + 1, ruta + [candidatos[i]], respuesta, ) candidatos = [10, 1, 2, 7, 6, 1, 5] objetivo = 8 print(Solución().combinationSum2(candidatos, objetivo))

Medio

Pitón

Artículos relacionados