问题标签 [recursive-backtracking]

我正在尝试生成所有可能的数字，这些数字以我不希望出现的数字向量超过它们在该向量中出现的次数。我的第一个想法是回溯，但如何.... 例如：3 7 5 => 3 5 7 35 37 53 57 73 75 357 375 537 573 735 753

我正在研究递归查找 3 位数的所有排列。

我厌倦了编写以下排列方法：

我试图涵盖所有案例，每个步骤都有细节，但我仍然突然收到堆栈溢出异常。

我感谢您的贡献，所以感谢转发。

此代码尝试解决 4 个皇后问题，将 4 个皇后放在 4*4 棋盘上，而其中任何一个都不能互相捕获

假设我有一个这样的板

x 使用框和 '.' 免费的。我需要把三联管填满所有区域，所以不会有空闲的单元格。三联牌是 L 形的，我用相同的数字标记相同的三联牌。

所以解决方案可能是这样的：

可能的回溯 python 算法可能是什么？

在网格中生成迷宫的最佳算法是什么？

我听说过 Kruskal 的算法和递归回溯器等，但它们都依赖于墙壁。在整个细胞是墙壁的情况下，创造惊奇的最佳算法是什么？

对于学校，我应该使用递归回溯来解决船难题。用户输入船的最大重量、物品类型的数量以及每种物品类型的重量和价值。每种物品类型中都可以放置一个以上的物品。

我们的任务是“程序应该找到一个解决方案，用选定的有价值的物品装满船，使船上物品的总价值最大化，而物品的总重量保持在船的承重范围内。”

它还具有用于递归回溯算法的非常具体的模板。

目前我正在使用连续的项目列表来存储可能的项目和船上的项目。item 结构包括重量、值、计数（使用次数）的 int 成员和用于打印目的的唯一代码。然后我有一个 Boat 类，其中包含数据成员 max_weight、current_weight、value_sum 和每个连续列表的成员，然后是解决难题所需的成员函数。我的所有类函数似乎都运行良好，并且在给定示例输入的情况下，我的递归确实显示了正确的答案。

我想不通的是额外得分的条件，即“修改你的程序，使其显示总权重最低的最佳解决方案。如果有两个总权重相同的解决方案，打破通过选择其中项目最少的解决方案来打成平手。” 我已经看了一段时间，但我只是不确定如何更改它以确保重量最小化同时也最大化价值。这是我的解决方案的代码：

所有函数的功能几乎完全符合其名称。如果船上没有任何可能的物品，则不再返回 true。Size 返回可能项目列表的大小。添加和删​​除项目会相应地更改项目计数数据以及 Boat current_weight 和 value_sum 成员。此外，add_item、remove_item 和 can_place 参数是正在使用的可能项目的索引。为了确保找到最大值，可能项目的列表在 Boat 的构造函数中按值降序排序，该构造函数将可能项目列表作为参数。

这里还有一个输入和输出的例子：

非常感谢任何见解！

我已经编程了大约五年了，我在创建动态迷宫时没有遇到任何问题。但是现在谈到递归回溯，我完全不知道从哪里开始。我已经阅读了很多教程、主题和一些算法维基（dijkstra 的算法），它们对我来说毫无意义。

我知道基本递归是如何工作的，但我根本无法理解如果不（在我看来）存储先前搜索的路径或者如果正在跟踪的路径突然分成两部分会发生什么情况下递归回溯是如何可能的。

我的程序是这样工作的：迷宫由 484 个面板组成（Panel[] 数组名为 mazeTiles）。有 22 行，每行有 22 个面板。黑色面板背景是墙壁，白色面板是可穿越的。

这是它在运行时的样子（并且只有在没有从起始方块（红色）到左上角绿色方块的有效路径时才会显示错误消息：

http://postimg.org/image/6c7wgxtz1/

显示的错误消息是“迷宫无法解决”，即使它可以清楚地解决。此错误消息位于 Button2_Click 方法中。

下面是我从教程中获取的代码（并修改过），问题肯定出在方法中，但我不知道如何解决这个问题。

我需要找到并存储从红色方块到绿色的所有路径或最快的路径（并且只标记最快的路径）。绿色方块是静态的，而红色方块和整个迷宫是随机生成的。

给定一个数组和一个目标（数字），我必须确定是否可以通过添加数组中的元素来达到目标​​。这是我的代码（在 javascript 中）和一些结果：

调用 check(6,[1,3,5]) 后我期望 add() 堆栈发生什么

实际结果：

它永远不会离开第一个分支！为什么 ？ 编辑： 好的，根据建议，我想最好避免将数组作为参数传递：

它在这里工作正常。

生成括号
给定 n 对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定 n = 3，解集为：

“((()))”、“(()())”、“(())()”、“()(())”、“()()()”

---

就个人而言，我认为
时间复杂度
= O(n!)（不包括复制 tmpStr 的时间），n 是输入，
= O(n * n!)（包括复制 tmpStr 的时间）。

空间复杂度
= O(n)（堆栈空间使用），
= O(n)（堆栈 + 递归空间使用）。

---

代码：Java

分词（使用动态编程：Top->Down）
给定一个字符串 s 和一个单词字典 dict，在 s 中添加空格来构造一个句子，其中每个单词都是一个有效的字典单词。

返回所有这些可能的句子。

例如，给定
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"]。

一个解决方案是[“猫和狗”，“猫沙狗”]。

---

问题：

• 时间复杂度？
• 空间复杂度？

我自己觉得，

• 时间复杂度 = O(n!)，没有动态规划，n 是给定字符串的长度，
• 空间复杂度 = O(n)。

困惑的：

• 无法用动态规划计算时间复杂度。
• 看来上面的空间复杂度是不正确的。

---

代码[Java]