如何調整代碼以使用回溯算法來解決組合問題

Question

問題描述：

返回數組的所有組合。例如有一個數組[1,2,3]，其結果是：

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

是的我知道有很多方法可以解決這個問題。但我正試圖用回溯算法來解決它。下面是我的代碼：

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 

它返回[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [3, 2]]，其中有一個錯誤的答案[3, 2]

從我的理解，DFS +回溯只能穿越其中從左到右一個方向排列。但很明顯[3,2]是相反的方向。

如何理解這個以及如何用我的代碼解決這個問題？

Answer 1

您的算法使用布爾值列表來跟蹤哪些元素被選中。但是這不是一個好的方法：一旦你選擇了一個元素我，你應該確保你只能選擇索引爲j> i的元素。

你似乎這樣做與start_idx，但實際上在遞歸調用你*只增加start_idx。

所以速戰速決是設置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

現在，這產生visited過時了，所以我們可以刪除這些檢查：

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

話雖這麼說，我會建議使用itertools.combinations。