python回溯算法

Question

如何利用python回溯算法求不等式的所有整数解呢，搞不懂回溯是什么意思

Answer 1

举个例子： 求 3x+2y<25的正整数解

def Solution(nums):
    def backtrack(nums, path, start):
        # 将满足条件的path添加到res结果中
        if len(path)==2:  # 不等式条件 和 变量个数
            t = tuple(path.copy())
            if t[0]*3+t[1]*2<25:
                res.append(t)
            if t[1]*3+t[0]*2<25:
                res.append(t[::-1])
            if t[0]*3+t[0]*2<25:
                res.append((t[0],t[0]))
            if t[1]*3+t[1]*2<25:
                res.append((t[1],t[1]))
        # 当前能够选择的参数列表
        for i in range(start, len(nums)):
            # 做选择
            path.append(nums[i])
            backtrack(nums, path, i+1)
            # 撤销选择
            path.pop()
    res = []
    backtrack(nums, [], 0)
    return set(res)
 
print(Solution([*range(1,13)]))  #估算大致解的范围，定的太大，计算有点慢

解集：
{(3, 4), (4, 3), (3, 1), (3, 7), (5, 4), (4, 6), (5, 1), (2, 2), (1, 6), (2, 5), (1, 3), (1, 9), (2, 8), (6, 2), (7, 1), (4, 2), (4, 5), (3, 3), (3, 6), (5, 3), (2, 4), (1, 2), (2, 1), (2, 7), (1, 5), (6, 1), (1, 8), (3, 2), (4, 1), (3, 5), (5, 2), (4, 4), (1, 1), (1, 4), (2, 3), (2, 9), (1, 7), (2, 6), (1, 10), (6, 3)}

请参见：

算法之【回溯算法】详解(python)_阿_旭的博客-CSDN博客_python回溯算法 回溯算法定义回溯算法实际上**基于DFS(深度优先搜索)**的一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回到上一个状态，尝试其他的路径，这种走不通就退回再走的技术为回溯法；满足回溯条件的某个状态的点称为“回溯点”。回溯相关问题DFS 和回溯算法区别DFS 是一个劲的往某一个方向搜索,直到到达最底层，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的 https://blog.csdn.net/qq_42589613/article/details/110801312