es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

Añadir Lista de Subresultados a Lista de Resultados

30 Jul, 2023 Programación

Estoy tratando de resolver el problema de Leetcode Combinations Sum y lo hice usando el método de recursión. Adjunto aquí mi enfoque:

def combinationSum(candidates,target):
    N = len(candidates)
    FinRes = []
    SubRes = []
    def Helper(Ind,candidates,target,FinRes,SubRes):
        if(Ind == len(candidates)):
            if(target == 0):
                FinRes.append(SubRes.copy()) # Agregando SubRes a FinRes
            return
        if(candidates[Ind] <= target):
            SubRes.append(candidates[Ind])
            Helper(Ind,candidates,target-candidates[Ind],FinRes,SubRes)
            SubRes.pop()
        Helper(Ind+1,candidates,target,FinRes,SubRes)

Helper(0,candidates,target,FinRes,SubRes)
return FinRes

candidates = [2,3,6,7]
target = 7
print(combinationSum(candidates,target))

En mi función de recursión, en el caso base cuando target==0, estoy agregando mi SubRes a FinRes. Intenté FinRes.append(SubRes) pero no se agrega a FinRes (en realidad se agrega y se elimina luego). Cuando hice SubRes.copy() funcionó bien. Entonces, ¿cómo puedo agregar SubRes con solo append?

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Cuando haces FinRes.append(SubRes) en el caso base, en realidad estás agregando la referencia de SubRes a FinRes. Más tarde, cuando haces SubRes.pop(), se elimina el último elemento de SubRes y como FinRes todavía tiene la referencia a SubRes, también se elimina el último elemento de FinRes.

    Para evitar esto, puedes hacer una copia de SubRes antes de agregarlo a FinRes usando FinRes.append(SubRes.copy()). De esta manera, estás agregando una nueva lista con los mismos elementos que SubRes a FinRes en lugar de su referencia.

    Si aún quieres usar append sin crear una copia, puedes crear una nueva lista en cada llamada recursiva. Esto se puede hacer cambiando el tipo de parámetro SubRes de lista a tupla y agregando una nueva lista vacía en cada llamada recursiva.

    Por ejemplo, puedes modificar tu código así:

    def combinationSum(candidates,target):
    N = len(candidates)
    FinRes = []
    SubRes = ()

    def Helper(Ind,candidates,target,FinRes,SubRes):
        if(Ind == len(candidates)):
            if(target == 0):
                FinRes.append(list(SubRes)) # Convirtiendo la tupla a lista antes de agregar
            return
        if(candidates[Ind] <= target):
            SubRes = SubRes + (candidates[Ind],) # Agregando un nuevo elemento a la tupla
            Helper(Ind,candidates,target-candidates[Ind],FinRes,SubRes)
            SubRes = SubRes[:-1] # Eliminando el último elemento de la tupla
        Helper(Ind+1,candidates,target,FinRes,SubRes)

    Helper(0,candidates,target,FinRes,SubRes)
    return FinRes

candidates = [2,3,6,7]                                                                                              
target = 7
print(combinationSum(candidates,target))

Comments are closed.