comment ajuster le code pour utiliser l'algorithme de retour arrière pour résoudre le problème de combinaison

Question

Description du problème:

Retourne toutes les combinaisons d'un tableau. par exemple, il y a un tableau [1, 2, 3], ses résultats sont:

[] 
[1] [2] [3] 
[1, 2] [1, 3] [2, 3] 
[1, 2, 3] 

Oui, je sais qu'il ya beaucoup de façons de résoudre ce problème. mais j'essaye de le résoudre avec l'algorithme de retour arrière. ci-dessous est mon code:

def p(arr): 
    ret = [] 
    #using visited boolean array to avoid duplicate traverse and backtracking. 
    visited = [False] * len(arr) 
    def dfs(start_idx, temp) 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      if not visited[i]: 
       visited[i] = True 
       dfs(start_idx + 1, temp + [arr[i]]) 
       visited[i] = False 
    dfs(0, []) 
    return ret 

Il retourne [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [3, 2]], qui a une mauvaise réponse [3, 2]

De ma compréhension, DSF + retours en arrière ne doit parcourir le tableau dans une direction qui est de gauche à droite. mais clairement [3, 2] est la direction inverse.

Comment comprendre cela et comment résoudre ce problème avec mon code?

Answer 1

Votre algorithme utilise une liste de booléens pour garder la trace des éléments sélectionnés. Mais ce n'est pas la bonne façon de le faire: une fois que vous avez sélectionné un élément i, vous devez vous assurer que vous ne pouvez sélectionner que des éléments avec un index j> i.

Vous semblez faire cela avec start_idx, mais en fait, dans l'appel récursif vous * n'augmentez que start_idx.

donc une solution rapide est de mettre start_index-i+1:

def p(arr): 
    ret = [] 
    #using visited boolean array to avoid duplicate traverse and backtracking. 
    visited = [False] * len(arr) 
    def dfs(start_idx, temp): 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      if not visited[i]: 
       visited[i] = True 
       dfs(i + 1, temp + [arr[i]]) # i instead of start_idx 
       visited[i] = False 
    dfs(0, []) 
    return ret

Cela donne maintenant visited obsolète, donc nous pouvons supprimer ces contrôles:

def p(arr): 
    ret = [] 
    def dfs(start_idx, temp): 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      dfs(i + 1, temp + [arr[i]]) 
    dfs(0, []) 
    return ret

Cela dit, je suggère d'utiliser itertools.combinations.