电力建设工程质监总站网站,做阀门销售在哪个网站上做好,如何设计个人网页,哪里可以检测丙型肝炎复习一下#xff1a; 回溯法解决的问题都可以抽象为树形结构。回溯法解决的都是在集合中递归查找子集#xff0c;集合的大小就构成了树的宽度#xff0c;递归的深度#xff0c;都构成的树的深度。 对于同一层而言#xff0c;其儿子都是等价的不同情况#xff0c;因此当儿… 复习一下 回溯法解决的问题都可以抽象为树形结构。回溯法解决的都是在集合中递归查找子集集合的大小就构成了树的宽度递归的深度都构成的树的深度。 对于同一层而言其儿子都是等价的不同情况因此当儿子处理完之后儿子应该回撤使得本层能继续遍历其他儿子。同理本层应当回撤当父亲结点遍历其他儿子。 代码随想录回溯 对于排列组合的回溯问题由于每一层当前集合中的每一个数都能被选择构成不同的情况因此函数体用for循环遍历选择元素让不同元素依次排在答案中本层的“第一位”往下遍历。如果是子集问题可以在本层按顺序选择下一层就不再选择本层之前被忽略的元素。但是本题不同本题需要考虑右括号和左括号配对的情况不能简单遍历元素。 由于左括号的数量大于右括号的数量时必然可以放右括号并且左括号随时可以放。本题采用分情况的回溯方式 ①有左括号时放左括号继续递归 ②剩余可放右括号的数量剩余可放左括号的数量时放右括号继续递归。 结束条件左右括号剩余数量都为0 为了不影响父节点继续分情况讨论必须pop出栈。 例如 第一层 压入( 第二层 压入) 第三层 压入( 并处理完之后未弹出 返回第二层 第二层 弹出末尾的(而实际上应该弹出)才对 回溯 提速的两个细节 ①同时为0可以用位运算 ②vector使用emplace_back() class Solution {
public:void back_tracking(int left,int right){if(!(left|right)){ans.emplace_back(cur);return;}if(rightleft){cur.push_back());back_tracking(left,right-1);cur.pop_back();}if(left){cur.push_back(();back_tracking(left-1,right);cur.pop_back();}return;}vectorstring generateParenthesis(int n) {back_tracking(n,n);return ans;}
private:vectorstring ans;string cur;
};
