回溯算法

tags: Math,backtracking,LeetCode101 Backtracking and stack overflow Intuition: We can abstract all the operations to a Tree, then apply DFS on it. For example: startValue=2, target=3, the tree looks like: /* 2 /\ / \ / \ 1(-1) 4(x2) /\ /\--+ / \ / \ 0(-1) 2(x2) 3(-1) 8(x2) */ class Solution { public: int brokenCalc(int startValue, int target) { unordered_set<int> visited; return backtracking(0, startValue, target, visited); } int backtracking(int count, int val, int target, unordered_set<int> & visited) { if (val == target) { return count; } if (visited.find(val) != visited.end()) { return -1; } int left = -1, right = -1; count++; visited.insert(val); if (val > 0) { left = backtracking(count, val - 1, target, visited); } if (val <= target * 2) { right = backtracking(count, val * 2, target, visited); } visited.erase(val); if (left != -1 && right != -1) { return min(left, right); } else if (left != -1) { return left; } return right; } }; Change target to startValue class Solution { public: int brokenCalc(int startValue, int target) { int r = 0; while (target > startValue) { target = target % 2 > 0 ? target + 1 : target / 2; r++; } return r + startValue - target; } };

tags: LeetCode,backtracking https://leetcode.com/problems/path-sum-ii/ /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> pathSum(TreeNode* root, int targetSum) { vector<vector<int>> r; if (root == nullptr) { return r; } if (root->left != nullptr) { auto left = pathSumSide(root-> left, root->val, targetSum); if (left.size() > 0) { left.insert(left.begin(), root->val); r.push_back(left); } } if (root->right != nullptr) { auto right = pathSumSide(root->right, root->val, targetSum); if (right.size() > 0) { right.insert(right.begin(), root->val); r.push_back(right); } } return r; } vector<int> pathSumSide(TreeNode* node, int sum, int targetSum) { vector<int> r; sum += node->val; if (node->left == nullptr && node->right == nullptr) { if (sum == targetSum) { r.push_back(node->val); return r; } } if (node->left != nullptr) { auto ret = pathSumSide(node->left, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } if (node->right != nullptr) { auto ret = pathSumSide(node->right, sum, targetSum); if (ret.size() > 0) { ret.insert(ret.begin(), node->val); return ret; } } return r; } }; 失败的错误用例: ...

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens-ii/ 参见：LeetCode: 51. N-Queens

tags: LeetCode,backtracking source: https://leetcode.com/problems/n-queens/ 一旦一个 Queue 被放置，那么横轴、纵轴、对角线都不再允许放置。我们按行进行遍历，所以我们需要跟踪以下位置是否已经放置 Queue： 纵轴（Column）：cols 主对角线（Positive Diagonal）：posDiag 次对角线（Negative Diagonal）：negDiag 纵轴很好记录，但是对角线比较困难，我们先来看一下对角线的特征，假设横轴为 r 纵轴为 c ， r - c 在正对角线是一致的： 斜对角线 r + c 是一致的: class Solution { public: vector<vector<string>> solveNQueens(int n) { for (int r = 0; r < n; r++) { string col = string(n, '.'); track.push_back(col); } backtracking(0, n); return res; } private: set<int> cols; // c set<int> posDiag; // r - c set<int> negDiag; // r + c vector<vector<string>> res; vector<string> track; void backtracking(int r, int n) { if (r == n) { res.push_back(track); return; } for (int c = 0; c < n; c++) { if (cols.find(c) != cols.end() || posDiag.find(r - c) != posDiag.end() || negDiag.find(r + c) != negDiag.end()) { continue; } cols.insert(c); posDiag.insert(r - c); negDiag.insert(r + c); track[r][c] = 'Q'; backtracking(r + 1, n); track[r][c] = '.'; cols.erase(c); posDiag.erase(r - c); negDiag.erase(r + c); } } }; 结果 ...

tags: LeetCode,backtracking 视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo 在 LeetCode: 46. Permutations 的基础上增加重复的元素。感觉不能依赖于 track + map 的去重逻辑回溯。 class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> res; } }; 数据特征： Value: 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, Index: 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 1, 0, class Solution { public: vector<vector<int>> permuteUnique(vector<int>& nums) { set<vector<int>> res; vector<vector<int>> ret; int n, i; vector<vector<int>> perms; if (nums.size() == 1) { ret.push_back(nums); return ret; } for (i = 0; i < nums.size(); i++) { n = nums.back(); nums.pop_back(); perms = permuteUnique(nums); for (auto perm : perms) { perm.push_back(n); res.insert(perm); } nums.insert(nums.begin(), n); } for (auto r : res) { ret.push_back(r); } return ret; } };

tags: LeetCode,backtracking Keywords backtrack 回溯算法 图解 举例： [1, 2, 3] ，顺着叶子节点和删除的节点就可以还原成全排列。 从上面图可以看出来，叶子节点加上回溯路径上被移除的节点就是结果的一项，从左到右依次是： [3,R:2,R:1] -> [3,2,1] [2,R:3,R:1] -> [2,3,1] … class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> track; backtrack(res, track, nums); return res; } void backtrack(vector<vector<int>> & res, vector<int> & track, vector<int>& nums) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); i++) { if (visited.find(nums[i]) != visited.end() && visited[nums[i]]) { continue; } track.push_back(nums[i]); visited[nums[i]] = true; // go into next level backtrack(res, track, nums); visited[nums[i]] = false; track.pop_back(); } } private: map<int, bool> visited; }; 根据视频解析：https://www.youtube.com/watch?v=s7AvT7cGdSo ...