回溯法介绍

递归，是计算机科学和数学中的一个基本概念，它是一种既迷人又强大的技术，通过将复杂问题分解为更简单、更易于管理的子问题来解决。递归一词源自拉丁语“recursion”，意为“返回”，它深刻地融入了计算机编程和数学思维的结构之中。在本篇文章中，我们将深入探讨递归的迷人世界，理解其原理、应用以及它在各个领域产生的深远影响。

其核心在于，递归是一个函数调用自身来解决问题的过程。这种自指的特性使递归区别于传统的迭代方法。想象一套俄罗斯套娃，每个娃娃里面都装着一个小一点的娃娃。递归也是如此，问题被分解成更小的、相似的子问题，而这些子问题又可能被进一步细分，直到达到一个基本情况——即问题变得微不足道可以解决的条件。随着每个子问题得到解决，结果会被组合起来解决原始问题。

递归最典型的例子之一是斐波那契数列，其中每个数字是前两个数字之和（例如：0, 1, 1, 2, 3, 5, 8, 13, ...）。斐波那契数列是递归定义的，因为每一项都依赖于其前一项的值。要计算第n个斐波那契数，可以使用递归算法，例如编程中的经典斐波那契函数。

递归不仅限于数学；它在计算机科学和编程中起着至关重要的作用。它是数据结构中的一个基本概念，尤其是在树和图结构中。例如，深度优先搜索和二叉树遍历等树遍历算法严重依赖递归来导航复杂的数据结构。同样，在目录遍历等任务中，递归函数至关重要，因为一个文件夹可能包含子文件夹，每个子文件夹都需要进行相同的操作。

递归在组合学相关问题的解决中也得到了广泛应用，例如生成排列和组合，这在密码学、统计学和博弈论等各个领域都至关重要。递归解决方案的优雅和简洁性使其在这些场景中具有极高的价值。

此外，递归是Lisp、Haskell和Scheme等函数式编程语言的组成部分。在这些语言中，递归函数比迭代循环更受青睐，它们促进了更具声明性和简洁性的编码风格。这与函数式范式对不变性和无副作用的强调相一致，而这通常通过递归来实现最佳。

除了技术应用，递归对我们理解复杂系统和现象产生了深远的影响。在自然科学中，递归结构可以在分形中观察到，其中相似的模式在不同尺度上重复出现，例如在Mandelbrot集或树的枝干中。在语言学中，递归被认为是人类语言的标志，因为可以通过嵌入从句来无休止地扩展句子。

尽管递归优雅且用途广泛，但并非没有挑战。递归算法可能比迭代算法效率低，因为函数调用的开销以及在处理大型数据集时可能发生堆栈溢出的风险。然而，像记忆化（缓存中间结果）这样的优化技术可以缓解这些问题，使递归解决方案更加实用。

总之，递归是一个迷人且不可或缺的概念，它渗透到从数学、计算机科学到自然科学和语言学等各个知识领域。它能够将复杂问题分解为简单的子问题，加上其优雅和简洁性，使其成为解决问题和理解我们周围世界的宝贵工具。在本次探索中，我们将深入研究递归的原理、技术和现实世界应用，揭示其美丽与复杂性。

回溯

回溯法是一种强大的算法技术，用于解决计算机科学和数学中广泛的复杂问题。它是一种系统的方法，通过逐步做出选择，并在必要时撤销这些选择以探索替代路径来帮助找到解决方案。这种方法特别适用于存在多种可能解决方案，但并非所有解决方案都满足特定约束或条件的问题。

回溯法的精髓在于通过做出明智的决策并在选择的路径导致死胡同时回溯，从而有效地探索大型解空间。它通常被比作树状结构，其中每个节点代表一个决策点，分支代表可能的选择。回溯法探索这个选择树，直到找到一个有效的解决方案或确定不存在解决方案。

回溯过程可分为几个关键步骤：

1. 初始化：算法从初始状态或部分解决方案开始，通常表示为空容器或空白画布，具体取决于问题。它还设置任何必要的数据结构来跟踪选择和约束。
2. 探索：在每个决策点，算法从一组可用选项中做出一个选择。这个选择可能涉及从列表中选择一个元素、在棋盘上放置一个对象，或与特定问题相关的任何决策。
3. 检查：做出选择后，算法会检查它是否满足问题的约束和条件。如果当前选择到目前为止是有效的，算法将继续进行下一步。否则，它将回溯到上一个决策点。
4. 递归：如果选择有效，算法将通过返回到探索步骤来递归地探索进一步的选择。这意味着它会深入决策树以探索新的可能性。
5. 回溯：如果在任何时候，算法遇到没有剩余有效选择的情况，或者意识到当前路径无法导致解决方案，它就会回溯到上一个决策点。这包括撤销最后一个选择，并探索替代路径。
6. 终止：算法重复步骤2到5，直到找到满足所有约束的有效解决方案，或者在没有找到解决方案的情况下耗尽所有可能的选择。在后一种情况下，它得出结论，对于给定的问题实例不存在解决方案。

回溯法是一种通用的技术，可以应用于各种问题领域，包括谜题、优化问题和搜索算法。可以使用回溯法解决的一些著名问题包括 N 皇后问题、数独、迷宫求解和图遍历。

效率是回溯算法的关键方面，因为选择和潜在路径的数量会随着问题规模的增长而呈指数级增长。通常采用剪枝技术来减少不必要的探索，从而提高算法的性能。这些技术包括提前检测无效路径并避免沿这些路径进行进一步探索。

总之，回溯法是一种系统且递归的算法技术，通过逐步做出选择并探索决策树，直到找到有效解决方案或耗尽所有可能性来解决复杂问题。它提供了一种优雅而高效的问题解决方法，是计算机科学和数学中的宝贵工具。

回溯法的关键组成部分

回溯法是一种强大的算法技术，用于系统地搜索具有多种可能选择和约束的问题的解决方案。其关键组成部分是：

• 决策空间：问题空间表示为树状结构，其中每个节点对应一个决策点。这些节点具有代表可能选择或选项的分支。算法探索此决策空间，逐步做出决策。
• 选择：在每个决策点，算法从一组可用选项中做出选择。这些选择对于找到有效解决方案或确定不存在解决方案至关重要。
• 约束：约束是解决方案必须遵守的规则或条件。在探索过程中，算法会检查当前选择是否满足这些约束。如果不满足，它就会回溯。
• 递归：回溯法涉及递归，因为算法通过递归地深入决策树来探索进一步的选择。这种递归过程允许系统地探索所有可能的路径。
• 检查和验证：做出选择后，算法通过验证当前状态是否满足问题的要求来检查它是否导向一个有效解决方案。如果选择有效，它将继续进行下一个决策点。否则，它将回溯。
• 回溯机制：当选定的路径导致死胡同或违反约束时，算法会回溯。这意味着它会撤销上一个选择，返回到上一个决策点，并探索替代选择。
• 终止条件：算法重复做出选择、检查和回溯的过程，直到找到满足所有约束的有效解决方案，或者在不成功的情况下耗尽所有可能的选择。终止条件定义了算法何时应停止。
• 剪枝：为了提高效率，通常会应用剪枝技术。剪枝涉及提前检测无效路径并避免沿这些路径进行进一步探索，从而减少不必要的计算工作。
• 优化：根据问题，可以将优化技术集成到回溯算法中，以找到最佳解决方案或优化特定的目标函数。
• 数据结构：回溯算法可能会使用数据结构来跟踪当前状态和选择，从而实现高效的检查和回溯操作。常见的数据结构包括堆栈、数组或递归函数调用。
• 解决方案累积：在某些情况下，算法会累积并记录所做的选择以构建最终解决方案。这在仅找到一个有效解决方案不足以解决的问题中尤其重要。

回溯算法的应用

回溯算法极其通用，在各种问题解决领域都有应用，其中必须通过一系列选择来找到解决方案，同时还要遵守特定的约束。在这里，我们将探讨回溯算法的一些常见应用：

1. 组合问题

• N 皇后问题：回溯法用于解决 N 皇后问题，即在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能互相威胁。算法探索不同的皇后放置组合，同时确保没有两个皇后在同一行、同一列或同一对角线上。
• 数独：数独谜题的解决涉及用数字填充一个 9×9 的网格，使得每一列、每一行以及九个 3×3 的子网格都包含从 1 到 9 的所有数字。回溯法用于尝试不同的数字放置，同时确保谜题保持有效。

2. 图问题

• 图着色：回溯法用于给图的顶点着色，使得没有两个相邻的顶点具有相同的颜色，同时尽量减少使用的颜色数量。这个问题在调度和优化任务中至关重要。
• 哈密顿回路：在图中寻找哈密顿回路，即访问每个顶点恰好一次的回路，是回溯法的另一个经典应用。算法探索图中的不同路径，直到找到哈密顿回路或确定其不可能。

3. 优化问题

• 旅行商问题 (TSP)：TSP 涉及找到访问一组城市一次并返回起点的最短可能路线。回溯算法探索不同的城市访问顺序以最小化总旅行距离。
• 背包问题：回溯法用于在遵守其重量限制的情况下，找到最大化背包价值的最佳物品组合。这个问题在资源分配和经济学中有应用。

4. 游戏求解

• 迷宫求解：回溯法通过做出探索不同路径的决策来导航迷宫。当遇到死胡同时，算法会回溯到上一个决策点并探索其他选项。
• 单词搜索：在单词搜索谜题中，回溯法用于在字母网格中查找隐藏的单词。算法探索网格中的不同路径，以水平、垂直或对角线找到单词。

5. 约束满足问题 (CSPs)

• 调度：CSPs 通常涉及在遵守各种约束的同时找到可行的调度。回溯法用于将任务或事件分配到时间段，同时确保所有约束都得到满足。
• 密码算术谜题：解决密码算术谜题（其中字母代表数字且方程必须得到满足）涉及回溯法以将值分配给字母以满足方程。

6. 子集生成

子集和：回溯法用于查找给定数字集中总和等于特定目标值的子集。这个问题出现在各种金融和资源分配场景中。

7. 字符串操作

生成排列和组合：回溯法用于生成给定元素集的所有排列或组合。这可应用于组合学、密码学和数据分析。

8. 人工智能中的回溯

• 约束传播：在约束满足问题中，回溯算法通过约束传播技术得到增强，以更有效地减少搜索空间。
• 游戏玩法：回溯法用于下棋或井字棋等游戏玩法算法，其中人工智能探索可能的走法及其后果，以确定最佳走法。

总之，回溯算法提供了一种强大而系统的方法来解决广泛的问题，这些问题跨越了各种领域。它们探索不同路径、遵守约束并在必要时有效回溯的能力，使它们在应对复杂且具有挑战性的计算任务方面具有无与伦比的价值。无论是解决谜题、优化路线，还是在人工智能中做决策，回溯法仍然是计算机科学家和问题解决者工具箱中的基本工具。

回溯算法中的挑战

回溯算法极其通用，但它们也带来了一系列挑战，需要加以解决才能有效而高效地解决问题。在这里，我们将讨论回溯时遇到的一些主要挑战以及潜在的优化措施。

1. 指数时间复杂度

• 挑战：回溯法的主要挑战之一是其潜在的指数时间复杂度。随着算法探索所有可能的选择，递归调用的数量会急剧增长，尤其是在决策点众多或解空间很大的问题中。
• 优化：剪枝是一项关键的优化技术，可以缓解这一挑战。通过在过程早期识别并消除无法导致有效解决方案的路径，剪枝减少了不必要的探索，并显著提高了性能。

2. 内存使用

• 挑战：回溯算法由于递归调用堆栈和用于跟踪选择和约束的数据结构，可能会消耗大量的内存。这对于输入规模很大的问题可能是一个问题。
• 优化：可以采用尾递归或迭代方法来最大限度地减少内存消耗。此外，优化数据结构并尽可能重用内存有助于减少内存开销。

3. 选择合适的数据结构

• 挑战：为跟踪选择和约束选择正确的数据结构对于高效回溯至关重要。使用不合适的数据结构可能导致性能缓慢和复杂性增加。
• 优化：为特定问题定制数据结构。例如，可以使用哈希表或集合来有效地检查约束或避免重新访问相同的状态。

4. 处理约束

• 挑战：确保约束得到有效检查和执行可能具有挑战性。对于具有复杂或众多约束的问题尤其如此。
• 优化：通过以结构化的方式组织约束来高效地实现约束检查。考虑使用约束传播技术来消除保证会违反约束的选择。

5. 选择正确的决策顺序

• 挑战：决策的顺序会极大地影响回溯算法的性能。决策顺序中的不良选择会导致效率低下的探索。
• 优化：尝试不同的决策顺序，并优先选择可能导致有效解决方案的选择。这可能需要特定于问题的启发式方法来指导算法。

6. 终止条件

• 挑战：确定何时终止回溯过程可能具有挑战性。设置正确的终止条件对于避免过度探索至关重要。
• 优化：根据问题的要求仔细定义终止条件。它应考虑诸如达到有效解决方案、耗尽所有选择或时间限制等因素。

7. 并行化

• 挑战：顺序回溯算法可能无法有效地利用多核处理器或分布式计算资源。
• 优化：实现回溯算法的并行或分布式版本，以利用多个处理器或机器，从而提高某些类问题的性能。

8. 内存管理

• 挑战：如果不妥善处理，可能会发生内存泄漏或内存管理效率低下，尤其是在处理动态内存分配时。
• 优化：使用适当的内存管理技术，例如垃圾回收或智能指针，以防止内存泄漏并在不再需要时高效地释放内存。

9. 算法复杂度

• 挑战：某些问题可能具有固有的高算法复杂度，而回溯法可能不是最有效的方法。
• 优化：当回溯法由于高复杂度而不可行时，请考虑替代算法或特定于问题的技术，例如动态规划、贪婪算法或近似算法。

总之，回溯法是一种强大的技术，用于解决各种问题，但它也带来与时间复杂度、内存使用、数据结构和约束处理相关的挑战。剪枝、高效数据结构、约束传播以及仔细的特定问题考虑等优化措施对于缓解这些挑战，使回溯算法在现实世界的问题解决中实用且高效至关重要。每个问题可能都需要量身定制的方法来达到最佳性能。

探索回溯法中的三种问题类型

回溯法是一种强大的算法技术，用于解决各种计算问题。它尤其适用于需要找到一组可能性中的一个或多个解决方案，同时遵守特定约束的情况。回溯法基于深度优先搜索原理，系统地探索潜在解决方案并在遇到死胡同时回溯。在本文中，我们将深入探讨回溯法常用的三种主要问题类型：决策问题、优化问题和枚举问题。

1. 决策问题

决策问题是一类计算问题，它需要一个简单的“是”或“否”的答案，表明是否存在一个可行的解决方案。回溯法通过探索解空间并遵守某些条件或约束来帮助我们确定这些解决方案的存在。以下是一些经常通过回溯法解决的决策问题示例：

a. N 皇后问题

N 皇后问题涉及在 N×N 的棋盘上放置 N 个皇后，使得任意两个皇后都不能互相威胁。该问题的决策版本是：“是否有可能在棋盘上放置 N 个皇后，使得没有两个皇后相互攻击？”回溯法可以系统地探索可能的皇后放置，如果找到有效的配置则返回“是”，如果不存在则返回“否”。

b. 子集和问题

在子集和问题中，给定一个正整数集合和一个目标和，目标是确定是否存在一个整数子集，其总和等于目标和。可以使用回溯法来探索集合中数字的各种组合，同时检查是否有任何子集等于目标和。

c. 图着色问题

图着色问题涉及给无向图的顶点着色，使得没有两个相邻的顶点具有相同的颜色。决策变体是：“是否可以使用最多 K 种颜色来给图着色？”回溯法可以通过递归地为顶点分配颜色并在遇到冲突时回溯来搜索有效的着色。

2. 优化问题

优化问题是指需要根据某个标准或目标函数在可行解决方案集中找到最佳解决方案的问题。回溯法可用于探索解空间并逐步细化搜索以找到最优解。以下是一些通过回溯法解决的优化问题示例：

a. 旅行商问题 (TSP)

TSP 涉及找到访问给定城市集合并返回起点的最短可能路线，每个城市只访问一次。回溯法可用于探索不同的城市访问顺序排列，并计算每个排列的总距离以找到最佳路线。

b. 背包问题

在背包问题中，有一组物品，每件物品都有重量和价值，还有一个最大重量容量的背包。目标是在不超过背包重量容量的情况下，选择一组物品来最大化总价值。回溯法可用于探索不同的物品选择，并确定在重量限制内产生最高价值的组合。

c. 数独谜题

数独是一种流行的数字谜题，您需要用数字填充一个 9x9 的网格，使得每一行、每一列和 3x3 的子网格都包含从 1 到 9 的所有数字，且不重复。回溯法可用于系统地填充网格单元，进行选择并在出现冲突时回溯，直到找到具有最多填充单元的解决方案。

3. 枚举问题

枚举问题涉及在给定约束条件下找到并列出问题的所有可能解决方案。回溯法特别适用于这些问题，因为它系统地探索整个解空间。以下是一些通过回溯法解决的枚举问题示例：

a. 排列

生成元素集的所有排列的问题涉及列出元素的所有可能排序。回溯法可通过交换元素并系统地生成所有排列来探索不同的排序。

b. 组合

组合涉及从更大的集合中选择一个元素子集，而不考虑选择的顺序。回溯法可通过系统地包含或排除元素来枚举所有可能的组合。

c. N 皇后解决方案

除了解决 N 皇后问题的决策版本外，回溯法还可用于枚举所有可能的解决方案。通过探索不同的皇后放置，您可以生成一个棋盘上皇后所有有效配置的列表。

总之，回溯法是一种通用的算法技术，可应用于包括决策问题、优化问题和枚举问题在内的广泛问题。它通过系统地探索解空间、做出选择并在必要时回溯来寻找有效解决方案、优化解决方案或枚举所有可能的解决方案。了解问题的性质以及所涉及的具体约束对于应用回溯法以确保高效且有效的问题解决至关重要。

基本术语

解向量

在问题解决方法中，解向量 X 代表问题实例的期望解决方案，通常由输入大小 n 表征。该向量包含来自有限可能解决方案集 S 的候选解决方案。

表示

解决方案可以简洁地表示为 n 元组 (X1, X2, ..., Xn)，其部分解决方案为 (X1, X2, ..., Xi)，其中 i 小于 n。

示例

例如，在 4 皇后问题中，解向量可以表示为 X = {2, 4, 1, 3}。

约束

约束在控制候选解决方案的值及其关系方面起着至关重要的作用。存在两种类型的约束：

• 隐式约束：这些规则用于识别解空间 S 中符合指定标准的解元组。隐式约束通常决定候选解决方案之间的关系。例如，在 N 皇后问题中，所有 xi 值都必须是不同的，以确保皇后不相互攻击。
• 显式约束：这些约束将候选解决方案 x_i 限制为基于问题实例的特定集合。显式约束可能因每个问题实例而异。例如，在 N 皇后问题中，如果 N = 4，x_i 可以属于集合 {1, 2, 3, 4}，而对于 N = 8，它属于集合 {1, 2, 3, 4, 5, 6, 7, 8}。

解空间

解空间 S 包括所有满足给定问题实例 P 的显式约束的候选解决方案 x_i。这个空间有效地由状态空间树中从根节点到各种节点的任何路径描述。

状态空间树

状态空间树作为特定问题实例 P 的解空间 S 的表示。这棵树有助于系统地探索解空间以确定所需的解决方案。

状态空间

状态空间包含状态空间树中从根节点到其他节点的任何路径，提供了潜在解决方案的全面视图。

问题状态

状态空间树中的每个节点都代表一个问题状态或部分解决方案，这是通过从根到该节点的选择来实现的。

解决方案状态

解决方案状态代表属于解空间 S 的问题状态。在具有可变元组大小的状态空间树中，所有节点都是解决方案状态，而在具有固定元组大小的树中，只有叶节点才具有此区分。

答案状态

答案状态是满足隐式约束的解决方案状态，最终定义了所需的解决方案或答案元组。

节点分类

• 有前途的节点：如果一个节点有可能导向所需的解决方案并对应一个可行的部分解决方案，则认为该节点有前途。如果部分解决方案变得不可行，则放弃该分支。
• 无前途的节点：一个无前途的节点最终会导致一个无法产生所需解决方案的状态，并被丢弃而不进一步探索。
• 活动节点：一个活动节点已被生成，但并非其所有子节点都已被探索。
• E-节点：E-节点是当前正在生成其子节点的活动节点。
• 死节点：死节点是指未进一步展开或其所有子节点都已生成的节点。

深度优先节点生成

此方法涉及将最新的活动节点作为下一个 E-节点。当生成当前 E 节点的子节点时，它就成为新的 E 节点。深度优先节点生成通常在回溯法中使用。

边界函数

边界函数（也称为有效性、标准或有前途函数）是应用于问题实例 (P) 的优化函数。它旨在在解空间内最大化或最小化特定标准（例如，背包问题中的利润），帮助消除不满足问题标准的候选解决方案。

状态空间树的类型

• 静态树：这些状态空间树的公式独立于具体的问题实例。
• 动态树：动态状态空间树的公式取决于正在解决的问题实例。

递归与回溯

递归涉及函数反复调用自身，直到达到基本情况。相比之下，回溯法利用递归来探索所有可能性，直到获得给定问题的最佳结果。

回溯算法：其思想是将皇后一个接一个地放在不同的列中，从最左边的列开始。当我们在一列中放置一个皇后时，我们会检查它是否与已放置的皇后发生冲突。在当前列中，如果我们找到了一个没有冲突的行，我们就将该行和列标记为解决方案的一部分。如果我们由于冲突而找不到这样的行，我们就回溯并返回 false。

回溯算法

• 生成 k 进制字符串
• 图着色问题
• 哈密顿回路
• N皇后问题
• 背包问题

回溯的伪代码

1. 递归回溯解决方案。

2. 查找是否存在解决方案

让我们尝试解决一个标准的回溯问题：N 皇后问题。

N 皇后问题是将 N 个国际象棋皇后放在 N×N 的棋盘上，使得任意两个皇后都不能互相攻击。例如，下面是 4 皇后问题的一个解决方案。

预期的输出是一个二进制矩阵，其中放置皇后的方块为 1。例如，下面是上述 4 皇后解决方案的输出矩阵。

代码

输出

. . Q . 
Q . . . 
. . . Q 
. Q . .	
Process executed in 1.11 seconds
Press any key to continue.

说明

1. 包含头文件

代码首先包含必要的头文件，包括 bits/stdc++.h，它包含了常用的标准头文件。

2. 声明答案向量

它声明了一个二维向量 answer，用于存储所有可能的解决方案，其中每个解决方案表示为字符串向量。

3. 定义 print_board 函数

此函数用于打印 answer 向量中存储的一个解决方案的棋盘配置。

4. 定义 safe 函数

safe 函数通过检查三个方向（同一列、左上对角线和右上对角线）来检查在给定棋盘位置放置皇后的安全性。

5. 定义 rec 函数

rec 函数是一个递归回溯函数，用于生成 N 皇后问题的所有可能解决方案。它一次在一行上放置皇后，必要时进行回溯。

6. 定义 solveNQueens 函数

solveNQueens 函数初始化一个空的棋盘，并调用 rec 函数来查找 N 皇后问题的所有可能解决方案。

7. 主函数

• 主函数是程序的入口点。
• 它调用 solveNQueens 来为 4x4 棋盘解决 N 皇后问题。
• 它打印找到的解决方案数量，并使用 print_board 函数显示一个解决方案。

总而言之，该代码使用回溯算法有效地解决了 N 皇后问题，并提供了一种在棋盘上可视化解决方案的方法。

时间和空间复杂度分析

提供的 N 皇后问题求解代码的时间和空间复杂度分析对于理解其效率和可伸缩性至关重要。

时间复杂度

• 该代码的时间复杂度主要取决于用于查找 N 皇后问题所有可能解决方案的递归回溯算法。让我们分析影响时间复杂度的关键因素：
• 递归回溯：代码的核心是 rec 函数，它使用递归回溯来探索棋盘上所有可能的皇后放置。对于每一行，它都会尝试该行中的所有可能位置。递归调用的数量与可能配置的数量成正比。
• 有效性检查：在每次递归调用中，safe 函数会检查在特定位置放置皇后的有效性。它会遍历列和对角线以确保没有冲突。在最坏的情况下，此函数会对每一行中的每个位置调用。
• 终止条件：递归会在找到解决方案（所有皇后都已放置）或检测到无效配置时停止。在最坏的情况下，它会在终止前探索所有可能的配置。
• 考虑到这些因素，时间复杂度是指数级的，通常为 O(N!)，其中 N 是棋盘的大小（行数和列数）。这是因为在第一行放置皇后的可能性有 N 种，在第二行有 N-2 种可能性（不包括第一行皇后威胁的列），在第三行有 N-4 种可能性，依此类推。这导致需要检查 N! 种可能的配置。

但是，safe 函数中的剪枝技术和提前退出条件可以帮助减少递归调用次数，从而在实践中提高算法的效率。平均而言，其性能优于最坏情况时间复杂度所暗示的。

空间复杂度

• 代码的空间复杂度由用于存储棋盘配置和输出解决方案的内存决定：
• 棋盘表示：棋盘表示为字符串向量（board）。它消耗 O(N^2) 的空间，因为它有 N 行 N 列。
• 输出解决方案：answer 向量存储所有可能的解决方案，每个解决方案表示为字符串向量。在最坏的情况下，当有 N! 个解决方案时，存储解决方案的空间复杂度为 O(N! * N^2)。
• 函数调用堆栈：递归函数调用堆栈所需的空间取决于递归深度，它等于行数 (N)。在最坏的情况下，由于调用堆栈而产生的空间复杂度为 O(N)。
• 综合考虑这些因素，由于存储解决方案，总体空间复杂度为 O(N! * N^2)，这占主导地位。

总之，由于对所有可能配置进行穷举搜索，该代码具有指数级时间复杂度（O(N!)），以及由于存储解决方案而具有 O(N! * N^2) 的空间复杂度。由于剪枝和提前终止条件，实际性能可能会好得多。