1.写出回溯法求解思路，求解步骤，剪枝函数类型，子集树的类型，递归回溯和迭代回溯框架

回溯法是一种通过不断尝试所有可能的解来求解问题的算法。其思路是从问题的初始状态开始，逐步地尝试所有可能的解决方案，直到找到一个符合要求的解，或者所有可能的解都被尝试完毕。

回溯法的求解步骤如下：

1. 定义状态空间：首先需要定义状态空间，即问题的解空间。状态空间是一个树形结构，每个节点表示一个问题的状态，根节点表示初始状态，叶子节点表示最终的解。

2. 定义扩展方式：对于每个状态，需要定义一种扩展方式，即从该状态出发可以扩展到哪些状态。扩展方式一般用一个函数来表示。

3. 定义剪枝函数：为了避免遍历整个状态空间，可以定义一些剪枝函数，用来剪掉一些不必要的搜索分支。剪枝函数可以根据问题的特点来设计。

4. 搜索状态空间：从初始状态开始，使用深度优先搜索的方式遍历整个状态空间，直到找到一个符合要求的解，或者所有可能的解都被尝试完毕。

回溯法的剪枝函数类型包括以下几种：

1. 可行性剪枝：当一个状态不满足问题的某些限制条件时，可以直接剪枝。

2. 最优性剪枝：当一个状态已经不可能成为最优解时，可以直接剪枝。

3. 对称性剪枝：当两个状态是对称的，只需要搜索其中一个状态即可，另一个状态可以直接剪枝。

回溯法的子集树可以分为两种类型：

1. 决策树：每个节点表示一个决策，每个分支表示一个可选的决策。

2. 状态树：每个节点表示一个状态，每个分支表示从该状态出发可以扩展到的其他状态。

回溯法可以使用递归回溯或者迭代回溯的方式实现。递归回溯的框架如下：

def backtrack(state):
    if is_solution(state):
        process_solution(state)
        return
    for next_state in expand(state):
        if is_valid(next_state):
            backtrack(next_state)

其中，`is_solution(state)`函数用来判断当前状态是否是一个解，`process_solution(state)`函数用来处理找到的解，`expand(state)`函数用来扩展当前状态，得到下一个状态的集合，`is_valid(next_state)`函数用来判断下一个状态是否合法。

迭代回溯的框架如下：

def backtrack(state):
    stack = [state]
    while stack:
        state = stack.pop()
        if is_solution(state):
            process_solution(state)
            continue
        for next_state in expand(state):
            if is_valid(next_state):
                stack.append(next_state)

其中，`stack`是一个栈，用来保存待处理的状态。其他函数的含义与递归回溯相同。