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

Question

问题描述：

Return一个数组的所有组合。比如有一个数组[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

它returns[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [3, 2]]，答案有误[3, 2]

根据我的理解，dfs + backtracking 应该只在从左到右的一个方向上遍历数组。但显然 [3, 2] 是相反的方向。

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

Answer 1

您的算法使用布尔值列表来跟踪 selected 的元素。但这不是这样做的好方法：一旦你 selected 一个元素 i，你应该确保你只能 select 具有索引的元素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。

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

how to adjust code to use backtracking algorithm to solve combination issue

python

algorithm

backtracking