fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
回溯算法最佳实践：括号生成 :: labuladong的算法小抄
Java版本：
class Solution {
List<String> res;
public List<String> generateParenthesis(int n) {
res = new ArrayList<>();
backtrack(new StringBuilder(),n,n);
return res;
}
private void backtrack(StringBuilder sb,int cntl,int cntr){
if(cntr<cntl) return;
if(cntl<0||cntr<0) return;
if(cntl==0&&cntr==0){
res.add(sb.toString());
return;
}
sb.append('(');
backtrack(sb,cntl-1,cntr);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
backtrack(sb,cntl,cntr-1);
sb.deleteCharAt(sb.length()-1);
}
}
@Warning-doid 看你怎么传递参数。所谓回溯，就是我们想要状态不变。如果用 pass-by-value 的形式来传参，数据本身是复制了，所以不用显式的撤回。如果是将共享的数据传，像例子里的 reference，就要显式的来回撤。
对于 @Warning-doid 的问题，@z1ggy-o 你其实没说到点子上，准确来说，关键是看你结束递归的 base case。
如果 base case 在叶子节点上结束，因为叶子结点也是一个节点，所以 base case 里面也要进行「选择」和「撤销选择」。
如果 base case 在空节点上结束，那就不用考虑这些，直接 return 就好。
class Solution {
private List<String> all = new LinkedList<>();
public List<String> generateParenthesis(int n) {
backtrack("", n, n);
return all;
}
private void backtrack(String now, int l, int r){
if(l+r==0){
all.add(now);
return;
}
if(l>0) backtrack(now+'(', l-1, r);
if(l<r) backtrack(now+')', l, r-1);
}
}
写了一个更轻快的版本，其中l和r分别代表还需要的左右括号数量
@Rayso777 你好，我也是小白，但我这样理解的，希望能帮到你。实质这就是在穷举呀。回溯算法的思路就是：1.算法过程中穷举所有组合（满足题目条件的组合/不满足题目条件的组合）；2.从所有组合中排除不满足条件的组合，最后得到满足条件的组合。放到这道题具体而言：1.在此位置先放左括号，进行backTrack递归，就相当于以左括号为根节点生成一棵子多叉树，当走到if(left==0&&right==0)时就可以记录下“正确的组合”，否则在if(left>right)和if(left<0||right<0)就返回了。2.撤销左括号，意思就是这棵子多叉树已经走完了，下面准备再试试在此位置放置右括号会有哪些“正确的组合”。3.右括号同理。
简单记录一下java版本
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new LinkedList<>();
StringBuilder sb = new StringBuilder();
backTrack(n,n,result,sb);
return result;
}
private void backTrack(int leftCount,int rightCount,List<String> result,StringBuilder sb){
//如果左括号剩下的多 说明不符合要求
if(leftCount > rightCount) return;
//括号数量最后 变成了 负数 不合法
if(leftCount < 0 || rightCount < 0) return;
if(leftCount == 0 && rightCount == 0){
result.add(sb.toString());//找到一种可能 将结果加入到result集合中
}
sb.append('(');
backTrack(leftCount-1,rightCount,result,sb);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
backTrack(leftCount,rightCount-1,result,sb);
sb.deleteCharAt(sb.length()-1);
}
}
简单记录一下java版本
class Solution { public List<String> generateParenthesis(int n) { List<String> result = new LinkedList<>(); StringBuilder sb = new StringBuilder(); backTrack(n,n,result,sb); return result; } private void backTrack(int leftCount,int rightCount,List<String> result,StringBuilder sb){ //如果左括号剩下的多 说明不符合要求 if(leftCount > rightCount) return; //括号数量最后 变成了 负数 不合法 if(leftCount < 0 || rightCount < 0) return; if(leftCount == 0 && rightCount == 0){ result.add(sb.toString());//找到一种可能 将结果加入到result集合中 } sb.append('('); backTrack(leftCount-1,rightCount,result,sb); sb.deleteCharAt(sb.length()-1); sb.append(')'); backTrack(leftCount,rightCount-1,result,sb); sb.deleteCharAt(sb.length()-1); } }
二刷补充说明，此处 为什么 eftCount > rightCount 就不符合要求了呢？因为题目中要想成对出现 ，左括号剩余数量始终要小于等于右括号剩余数量的，因为给出的例子中，左括号无非与右括号成对了或者左括号还没成对，那剩余的右括号就多了或者与左括号剩余相等的。
js版本
/**
* @param {number} n
* @return {string[]}
*/
/**
解题思路
1. 使用回溯算法，相当于生成一颗树
*/
var generateParenthesis = function(n) {
let res=[]
let track=[];
// left 括号数有n个， right 括号数也有n个
function backtrack(left,right,track){
if(left>right){ // 因为先消费的左边的，所以一定是左边的元素比右边的少
return ;
}
if(left<0||right<0){
return
}
if(left===0&&right===0){
res.push(track.slice().join(""));
return
}
track.push("(");
backtrack(left-1,right,track);// 消耗了一个左括号
track.pop();
track.push(")");
backtrack(left,right-1,track); // 消耗了一个右括号
track.pop();
}
backtrack(n,n,track);
return res
};
记录一下，利用的是之前排列组合的思想解题，利用的是排列 元素可重不可重选，之前做的时候误用了组合的思路导致不对，其实后面想来用组合的话不就是2n选2n个，那就只有一种情况，显然不符合题意
class Solution {
List<String> res = new LinkedList<>();
StringBuffer track = new StringBuffer();
int trackSum = 0;
boolean[] used;
public List<String> generateParenthesis(int n) {
//把"("看作1
//把")"看作-1
//每次放进去需判断sum >= 0 不然不对，肯定是'('先于')'
//相当于组合加上个TrackSum
int[] nums = new int[2*n];
used = new boolean[2 * n];
//存放括号代表的int值，前n个是1(左括号)，后n个是-1(右括号)
for(int i = 0; i < n; i++){
nums[i] = 1;
nums[i + n] = -1;
}
backtrack(nums,trackSum);
return res;
}
//排列 元素可重不可重复选
void backtrack(int[] nums, int trackSum){
if(nums.length == track.length()){
res.add(new String(track));
trackSum = 0;
return;
}
for(int i = 0; i < nums.length; i++){
//剪枝
if(used[i]){
continue;
}
if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
if(trackSum + nums[i] < 0){
//保证trackSum一直 >=0，也就是左括号比右括号数量多
//小于0就不用append这一次
continue;
}
//做选择
if(nums[i] == 1){
track.append('(');
}else{
track.append(')');
}
used[i] = true;
trackSum += nums[i];
//递归
backtrack(nums, trackSum);
//撤销选择
used[i] = false;
track.deleteCharAt(track.length() - 1);
trackSum -= nums[i];
}
}
}
Java版，使用LinkedList<Character>作为track，充分发挥双端队列优势，个人感觉比StringBuilder更容易理解和记忆。
class Solution {
public List<String> generateParenthesis(int n) {
// 可用的左括号和右括号数量初始化为 n
backtrack(n, n);
return res;
}
// 记录所有合法的括号组合
List<String> res = new LinkedList<>();
// 记录回溯的路径
LinkedList<Character> track = new LinkedList<>();
// 可用的左括号数量为 left 个，可用的右括号数量为 right 个
void backtrack(int left, int right) {
// 若左括号剩下的多，说明不合法
if (left > right) {
return;
}
// 数量小于 0 肯定是不合法的
if (left < 0 || right < 0) {
return;
}
// 当所有括号都恰好用完时，得到一个合法的括号组合
if (left == 0 && right == 0) {
res.add(applyAsString(track));
return;
}
// 尝试放一个左括号
// 做选择
track.addLast('(');
// 递归下一层回溯树
backtrack(left - 1, right);
// 撤销选择
track.removeLast();
// 尝试放一个右括号
// 做选择
track.addLast(')');
// 递归下一层回溯树
backtrack(left, right - 1);
// 撤销选择
track.removeLast();
}
String applyAsString(LinkedList<Character> track) {
StringBuilder sb = new StringBuilder(track.size());
for (Character ch : track) {
sb.append(ch);
}
return sb.toString();
}
}
贴一个C++双百版本，并且带for循环便于理解。实际上这里的for循环是可以省略的，因为同一个位置上只有两种情况: 左括号和右括号。前面带for循环是因为同一个位置的情况有k种，这里可以直接手写出来所以就省略for了
class Solution {
vector<string> res;
vector<char> dir {'(', ')'};
public:
void backtrack(int n, int left, int right, string& onPath) { // 放n个括号，代表左括号有n个，右括号也有n个，这样才合法。并且在每个位置i时，[0, i]中左括号的总数一定大于右括号的数量
if (left < 0 || right < 0) return;
if (right < left) return; // 如果右括号放的比左括号多，则不合法，返回
if (left == 0 && right == 0) {
res.push_back(onPath);
return;
}
for (auto a: dir) {
onPath.push_back(a);
if (a == '(') {
backtrack(n, left - 1, right, onPath);
} else {
backtrack(n, left, right - 1, onPath);
}
onPath.pop_back();
}
}
vector<string> generateParenthesis(int n) {
string onPath = "";
backtrack(n, n, n, onPath);
return res;
}
};
我是这么想的：每一次插入一对括号，这样绝对能成功，但是可能重复，所以我用set去重。时间复杂度也很大，应该是O(n^n)。
class Solution {
public:
set <string> ans;
vector <string> a;
set <string> f[10] = {};
void dfs(string a, int n)
{
if (n == 0)
{
// ans.insert(a);
this -> a.push_back(a);
return;
}
if (a == "")
{
dfs("()", n - 1);
return;
}
for (int i = 0; i < a.size(); i ++)
{
string temp = a.substr(0, i + 1);
temp += "()";
temp += a.substr(i + 1, a.size());
if (f[n].count(temp))
{
continue;
}
f[n].insert(temp);
dfs(temp, n - 1);
}
}
vector<string> generateParenthesis(int n)
{
dfs("", n);
// vector <string> ans;
// for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
// {
// ans.push_back(* i);
// }
// return ans;
return a;
}
};
哦，刚刚的好像是另一个思路，就是用set[]让每一步都不会重复，空间复杂度大，这才是那个set去重的版本：
class Solution {
public:
set
void dfs(string a, int n)
{
if (n == 0)
{
// ans.insert(a);
this -> a.push_back(a);
return;
}
if (a == "")
{
dfs("()", n - 1);
return;
}
for (int i = 0; i < a.size(); i ++)
{
string temp = a.substr(0, i + 1);
temp += "()";
temp += a.substr(i + 1, a.size());
if (f[n].count(temp))
{
continue;
}
f[n].insert(temp);
dfs(temp, n - 1);
}
}
vector<string> generateParenthesis(int n)
{
dfs("", n);
// vector <string> ans;
// for (auto i = this -> ans.begin(); i != this -> ans.end(); i ++)
// {
// ans.push_back(* i);
// }
// return ans;
return a;
}
};
使用括号数量递增
class Solution {
List<String> result = new LinkedList<>();
public List<String> generateParenthesis(int n) {
dfs(0,0,n,new StringBuilder());
return result;
}
private void dfs(int left , int right , int n,StringBuilder sb){
if(right > left) return;
if(left > n || right > n) return;
if(left == n && right == n){
result.add(sb.toString());
return;
}
sb.append('(');
dfs(left+1,right,n,sb);
sb.deleteCharAt(sb.length()-1);
sb.append(')');
dfs(left,right+1,n,sb);
sb.deleteCharAt(sb.length()-1);
}
}