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

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

您的算法使用布尔值列表来跟踪选择了哪些元素。但这不是这样做的好方法：一旦你选择了元素 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(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 .