关于回溯法【python】

Python016

关于回溯法【python】,第1张

最近遇到这么一个题目，给定一个数字集合a，和一个目标值t，找到集合a中所有和为t的数字组合，一个数字，可以多次出现。（集合和t都为正整数）

例子：

输入[2,3,6,7],t=7

输出：[[7],[2,2,3]]

#!/usr/bin/env python

candidate=[2,5,1]

list=[]

result=[]

def search(candidates,target,list):

       if (sum(list)==target): //回溯点

             list.sort()

             if list not in result:

                     result.append(list)

                              return

if (sum(list)>target):

return

for i in range(len(candidate)):

search(candidates,target,list+[candidates[i]])

search(candidate,7,list)

print(result)

可以使用回溯法枚举出符合条件的矩阵，以避免使用过多的for循环嵌套。代码如下：

#coding=utf-8

N = 3

matrix = [0, 0, 0, 0, 0, 0, 0, 0, 0]

# 打印矩阵

def printMatrix(matrix):

    for i in range(len(matrix)):

        print(matrix[i], end = ' ')

        if (i + 1) % N == 0:

            print()

# 判断矩阵是否符合要求，符合返回True，否则返回False

def isOk(matrix):

    for i in range(N):

        # 横向判断每行之和是否等于15

        sum = 0

        for j in range(N):

            sum = sum + matrix[N * i + j]

        if sum != 15:

            return False

        # 纵向判断每列之和是否等于15

        sum = 0

        for j in range(N):

            sum = sum + matrix[i + j * N]

        if sum != 15:

            return False

    # 判断两个对角线是否等于15

    if (matrix[0] + matrix[4] + matrix[8]) != 15:

            return False

    if (matrix[2] + matrix[4] + matrix[6]) != 15:

            return False

        

    return True

# 下面两个函数是使用回溯法枚举符合要求的矩阵

def check(matrix, index):

    for i in range(index):

        if matrix[i] == matrix[index]:

            return False

    return True

def enum(matrix, index):

    if index == len(matrix):

        if isOk(matrix):

            printMatrix(matrix)

            print()

    else:

        for i in range(1, len(matrix) + 1):

            matrix[index] = i

            if (check(matrix, index)):

                enum(matrix, index + 1)

if __name__ == '__main__':

    enum(matrix, 0)

运行结果：