如何调整代码以使用回溯算法来解决组合问题

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。