回溯算法Python代码

以下是回溯算法的Python代码示例：

<<引用>>
八皇后问题：

class Solution(object):
    def queens_num(self, n):
        # 矩阵为n行n列
        self.position([-1] * n, 0, n)

    def position(self, col, row, n):
        if row == n:
            print(col)
            return
        for i in range(n):
            col[row] = i
            if self.check(col, row):
                self.position(col, row + 1, n)

    def check(self, col, row):
        for i in range(row):
            if col[row] == col[i] or abs(col[row] - col[i]) == row - i:
                return False
        return True

<<引用>>
子集问题：

class Solution(object):
    def subsets(self, nums):
        """
        78.subsets nums不包含重复的数字，生成所有子集，包含空集
        """
        if len(nums) <= 0:
            return []
        nums.sort()
        res = []

        def _backtrace(num, pre_list):
            res.append(pre_list.copy())  # 无判断条件，直接加入
            for i in range(len(num)):
                pre_list.append(num[i])
                _backtrace(num[i + 1:], pre_list)
                pre_list.pop()

        _backtrace(nums, [])
        return res

    def subsetsWithDup(self, nums):
        """
        90. 子集 II
        """
        if len(nums) <= 0:
            return []
        nums.sort()
        res = []

        def _backtrace(num, pre_list):
            res.append(pre_list.copy())
            for i in range(len(num)):
                if i > 0 and num[i] == num[i - 1]:
                    continue
                pre_list.append(num[i])
                _backtrace(num[i + 1:], pre_list)
                pre_list.pop()

        _backtrace(nums, [])
        return res