backtracking 相关问题

回溯是用于找到某些计算问题的解决方案的通用算法，其逐步地为解决方案构建候选者。

LeetCode 39. 组合和 - 如何避免重复

我正在做leetcode 39.组合和：给定一组不同的整数候选者和一个目标整数目标，返回候选者的所有唯一组合的列表，其中所选数字...

python combinations depth-first-search backtracking

回答 2 投票 0

实现堆栈以对结构使用回溯

这是一个使机器人能够沿着黑线穿过“迷宫”的程序。迷宫由 7x7 的黑线组成，并有一条入口线穿过其中。可以有空的方块和引导线

c struct backtracking robotics

回答 1 投票 0

多次递归返回

我正在做leetcode 79 C++解决方案，你需要在2D矩阵中查找单词。我用回溯来做到这一点类解决方案{ 民众：布尔回溯（int row，int col，int N，向量我正在做leetcode 79 C++解决方案，你需要在二维矩阵中找到单词。我正在用回溯来做到这一点 class Solution { public: bool backtrack(int row, int col, int N, vector<vector<char>>& matrix, const string& word, const int num_rows, const int num_cols, const int word_size, bool& result) { if (word[N]==matrix[row][col]) //Letter in matrix equals current word letter { if (N==word_size or result) //BASE CASE: Reached end of word return result = true; map_been[row][col] = true; //Cell is used if (row!=0 and map_been[row-1][col]==0)} //Going up backtrack(row-1, col, N+1, matrix, word, num_rows, num_cols, word_size, result); if (col!=num_cols and map_been[row][col+1]==0)} //Going right backtrack(row, col+1, N+1, matrix, word, num_rows, num_cols, word_size, result); if (row!=num_rows and map_been[row+1][col]==0)} //Going down backtrack(row+1, col, N+1, matrix, word, num_rows, num_cols, word_size, result); if (col!=0 and map_been[row][col-1]==0)} //Going left backtrack(row, col-1, N+1, matrix, word, num_rows, num_cols, word_size-1, result); map_been[row][col] = false; //clean-up map } return result; } bool exist(vector<vector<char>>& matrix, string word) { int num_rows = matrix.size(); int num_cols = matrix[0].size(); int word_size = word.size(); bool result=false; vector<vector<bool>> map_been (num_rows, (vector<bool> (num_cols, false))) for (int i=0; i<num_rows; i++) for (int j=0; j<num_cols; j++) //starting from every matrix position { if (backtrack(i, j, 0, matrix, word, num_rows-1, num_cols-1, word_size, result)) return true; } return false; } }; 在每个递归步骤中，我有 4 个变体：向上、向左、向右或向下，每个步骤都会产生新的递归。我想知道当我找到整个单词（基本情况）时如何结束所有递归，因为现在当我找到它时，程序会继续向左、向右等计数。使用递归的结果，一旦成功就返回。您还可以移动有效性检查以简化流程，并使用参数的大小而不是传递它们。这里有一个不同的建议： bool backtrack(int row, int col, int N, const vector<vector<char>>& matrix, const string& word) { return N == word.size() // Found it. || ( // Validity checks. row >= 0 && row < matrix.size() && col >= 0 && col < matrix[0].size() && N < word.size() && word[N] == matrix[row][col] // Keep searching. && ( backtrack(row-1, col, N+1, matrix, word) || backtrack(row, col+1, N+1, matrix, word) || backtrack(row+1, col, N+1, matrix, word) || backtrack(row, col-1, N+1, matrix, word))); }

c++ recursion backtracking

回答 1 投票 0

Leetcode 1255-递归与回溯

我不太明白为什么当我们有第二个 for 循环来恢复 letterCount 时我们使用 .clone() 方法。当我在没有 .clone() 方法的情况下运行这段代码时，它给了我错误的答案.. .

java recursion dynamic-programming clone backtracking

回答 1 投票 0

使用回溯C++解决迷宫

我有这个二维矩阵迷宫。 “@”表示开始，“#”表示结束。 0表示路径被封锁，1表示可以通过。程序需要解决迷宫和原理...

c++ recursion backtracking maze recursive-backtracking

回答 1 投票 0

查找所有路径问题（Java中的递归和回溯）

我一直在关注 Java 数据结构和算法的播放列表，并且遇到了回溯主题，其中为您提供了一块板，以及起点 (0,0) 和终点...