问题标签 [recursive-backtracking]

This link has a Backtracking implementation of the Sudoku Solver algorithm. Notice how line number 42, reverts the value initially assigned to a cell, to another value, in case the initially assigned value did not give a valid output.

However, I don't understand how merely changing the value of that cell alone is sufficient. This call could've triggered many other calls, and since arrays (matrices) are passed by memory (reference), it does not keep a copy of the matrix (grid[N][N]) at every invocation of the recursive function, and so changes till the base case of the recursion will reflect even in the first frame of recursion by the time it returns back.

According to me, just before calling the recursive function, you should make a temporary copy of grid[N][N] and restore it as soon as the call gets returned, and before the next function in the same frame is called.

Something like

Please help me understand this detail.

我正在学习递归，但我需要有关如何开始制作算法的参考。我需要组织积木来使用所有的棋子，尽可能地填满棋盘。谢谢大家。

我使用 TPPAPI检查域可用性和域注册，但我在string.

1. 获取会话，返回字符串OK: t73484678463765

2. 域检查，返回字符串woohoo123.nz: OK: Minimum=1&Maximum=2

3. 在其他情况下，返回字符串woohoo123.nz: ERR: 102, This is message

当它返回时，OK它&在孩子身上，但当ERR它有,

我想将返回转换string为array

比如woohoo123.nz: OK: Minimum=1&Maximum=2下面的输入输出array

输入woohoo123.nz: ERR: 102, This is message输出如下array

我更喜欢重用代码，我更喜欢recursive但callback在这种情况下不确定。

我正在处理的问题在这里： http: //practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence

基本上我们得到了两个字符串，我们被要求找到最长的公共子序列。我在网上搜索了解决方案并将它们与我自己的解决方案进行了比较，但我在我的代码中找不到任何错误。我想知道为什么它仍然不起作用。

而且，我被要求通过使用递归方法来解决这个问题

这是我的代码：

以下是所有测试用例：

调用值返回

“ABCDEFG”、“BGCEHAF”、“BCEF”

“她卖”、“贝壳”、“卖”

“12345”、“54321 21 54321”、“123”

《白眼老师》、《好吃的桃子》、《各显神通》

“马蒂”、“海伦”“”

"","乔" ""

“苏西”、“”“”

“ACGGTGTCGTGCTA”、“CGTTCGGCTATCGTACGT”、“CGGTTCGTGT”

使用我的代码，我得到了所有测试用例的 StackOverFlow。

在给定的名为“data.in”的文件中写入了城市 N、两个城市 A 和 B 的数量以及它们之间的现有道路。例如，集合“2 6”表示城市 2 和城市 6 之间存在一条道路.我必须在一个名为“data.out”的文件中显示从城市 A 到达城市 B 的所有可能性，而无需多次经过一个城市。我已经编写了以下代码，但它没有打印任何内容。

编写一个使用递归回溯的方法 makeChange，使用便士（1 美分）、镍（5 美分）、10 美分（10 美分）和 25 美分（25 美分）找出给定金额找零的所有方法。

例如，当找 37 美分时，您可以使用：

• 1 季度
• 1 毛钱和 2 便士
• 3 角钱和 7 便士
• 或其他组合。

您的方法应该接受一个参数：要更改的美分数量。

您的方法的输出应该是每种类型硬币的所有组合的序列，加起来等于该数量，每行一个。

例如，如果客户端代码包含以下调用：

生成的整体输出应如下所示：

解决这个问题的一个关键见解是查看硬币的每种面额（便士、镍等）并尝试该硬币的所有可能数字（1 便士、2 便士、...、28 便士）来看看是什么可以从该选择开始进行组合。例如，在上面的输出中，首先显示所有以 3 便士开头的组合，然后显示所有以 8 便士开头的组合，依此类推。

由于回溯涉及探索一组选择，因此您应该在代码中以某种方式表示硬币面额。我们建议保留所有硬币面额值的列表以供处理。当您处理各种硬币值时，您可以修改此列表的内容。下面的模板是一个起点（您可以将其复制/粘贴到代码文本框中以开始使用）：

您可以假设传递给您的方法的更改量是非负的，但它可能超过 100。

所以这是我的代码：

及其调用 makeChange(28) 的输出：

...（有数百行输出）

有人能告诉我为什么会产生重复的输出吗？非常感谢！

我正在尝试打印字符串的所有排列。但是，尽管我尽了最大的努力，我还是无法为我的代码获得所需的输出。有人可以解释我的代码有什么问题吗？我已经尝试了很多小时，但惨遭失败。

以下代码的输出是：-

美国广播公司

这是回溯的置换函数：-

这是运行上述代码的主要功能：-

这是交换的代码：-

我遇到了提高我的编码技能的递归练习，并发现了以下问题。

给定一个整数数组，是否可以选择一组整数，使得该组总和为给定目标？我们的惯例不是查看整个数组，而是考虑从索引开始到数组末尾的数组部分。调用者可以简单地通过将 start 传递为 0 来指定整个数组。不需要循环——递归调用沿着数组向下进行。

经过2天的工作和学习，我什么都没有。我检查了给定的解决方案，但在逐步调试后我仍然无法理解解决方案。

解决方案很短，其逻辑是基于组合的。你怎么看待这件事？它背后的算法解释是什么？

问候

你如何找到递归回溯生成的迷宫的起点和终点？似乎很难弄清楚，因为迷宫从来没有ends。这会是你第一次开始回溯的地方吗？起点可能是您开始的地方，但有时会有更好的地方。

问题和算法的细节

给定一个 MxN 网格，从左上角单元格到达右下角单元格可以有多少条路径？在任何网格上，您可以向四个方向移动。唯一的限制是不能多次访问一个单元格。

我们可以使用回溯算法来解决这个问题，代码如下（参考）：

我知道什么？

我对使用替换方法和递归树方法（参考）计算递归算法的时间复杂度有一些了解。我可以计算一些更简单算法的时间复杂度（例如Fibonacci Sequence）。

在这里发布问题之前我做了什么？

我检查了this、this、this和许多其他链接。但是我无法将所有这些信息结合在一起并找出这个问题的时间复杂度。

我尝试使用递归树方法来计算时间复杂度。但是当 M&N 很大时路径可能会非常扭曲，我不知道如何扩展树，因为四个方向都允许。

读完后，我有一个粗略的想法，也许我可以根据剩余的网格来思考：

1. 第 1 步 - 有 MxN 个网格可供选择，因此有 MxN 个可能性。
2. 第 2 步 - 只有 MxN-1 个网格可供选择。所以我们有 (MxN)x(MxN-1)
3. 以此类推，直到未知的结局。

尽管如此，我还是不能完全理解这个算法的时间复杂度。

我想知道什么？

对于这样一个回溯算法，我们如何充分理解它的时间复杂度呢？

任何想法表示赞赏。