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

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 + backtracking 应该只在从左到右的一个方向上遍历数组。但显然 [3, 2] 是相反的方向。

如何理解这一点以及如何用我的代码解决这个问题？

Answer 1

您的算法使用 bool 值列表来跟踪选择了哪些元素。但这不是这样做的好方法:一旦你选择了一个元素 i，你应该确保你只能选择索引为 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(<b>i</b> + 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。