大部分的回溯都有一部分的重复搜索,可以通过一个备忘录记录之前搜索的结果,在找到这个节点的时候直接return就行
idx是一个很重要的指标,它的左边是 idx + 1 ~ n-1(i = idx + 1, idx + 2….n-1)
同时idx的子树对应的i也是 idx + 1 ~ n-1(i = idx + 1, idx + 2….n-1)
- 因此,使用idx和深度作为备忘录的key可以很好的保存这个节点
举例
link : https://leetcode.com/problems/combinations/description/
class Solution {
public:
vector<vector<int>> memo[21][21];
vector<vector<int>> combine(int n, int k, int cur=1) {
if(k == 0) return {{}};
if(!memo[k][cur].empty()) {
cout << k << "memo"<<cur;
return memo[k][cur];
}
vector<vector<int>> ans;
for(int i=cur; i<=n; i++){
cout << "before idx= "<< cur <<" before i=" <<i+1 << " k = "<<k-1<< " ;";
vector<vector<int>> temp = combine(n, k-1, i+1);
for(auto v: temp){
v.push_back(i);
ans.push_back(v);
}
cout << endl;
cout << "back idx= "<< cur <<" back i="<<i<< " k = "<<k<< endl;
}
cout << "end" << endl;
cout << endl;
for (auto a:ans){
cout << "[";
for (auto b:a) {
cout << b<<" ";
}
cout << "]";
}
cout << endl;
cout << "k=" << k << " idx = " << cur << endl;
// cout << cur << endl;
return memo[k][cur] = ans;
}
};
out :
before idx= 1 before i=2 k = 2 ;before idx= 2 before i=3 k = 1 ;before idx= 3 before i=4 k = 0 ;
back idx= 3 back i=3 k = 1
before idx= 3 before i=5 k = 0 ;
back idx= 3 back i=4 k = 1
before idx= 3 before i=6 k = 0 ;
back idx= 3 back i=5 k = 1
end
[3 ][4 ][5 ]
k=1 idx = 3
back idx= 2 back i=2 k = 2
before idx= 2 before i=4 k = 1 ;before idx= 4 before i=5 k = 0 ;
back idx= 4 back i=4 k = 1
before idx= 4 before i=6 k = 0 ;
back idx= 4 back i=5 k = 1
end
[4 ][5 ]
k=1 idx = 4
back idx= 2 back i=3 k = 2
before idx= 2 before i=5 k = 1 ;before idx= 5 before i=6 k = 0 ;
back idx= 5 back i=5 k = 1
end
[5 ]
k=1 idx = 5
back idx= 2 back i=4 k = 2
before idx= 2 before i=6 k = 1 ;end
k=1 idx = 6
back idx= 2 back i=5 k = 2
end
[3 2 ][4 2 ][5 2 ][4 3 ][5 3 ][5 4 ]
k=2 idx = 2
back idx= 1 back i=1 k = 3
before idx= 1 before i=3 k = 2 ;before idx= 3 before i=4 k = 1 ;1memo4
back idx= 3 back i=3 k = 2
before idx= 3 before i=5 k = 1 ;1memo5
back idx= 3 back i=4 k = 2
before idx= 3 before i=6 k = 1 ;end
k=1 idx = 6
back idx= 3 back i=5 k = 2
end
[4 3 ][5 3 ][5 4 ]
k=2 idx = 3
back idx= 1 back i=2 k = 3
before idx= 1 before i=4 k = 2 ;before idx= 4 before i=5 k = 1 ;1memo5
back idx= 4 back i=4 k = 2
before idx= 4 before i=6 k = 1 ;end
k=1 idx = 6
back idx= 4 back i=5 k = 2
end
[5 4 ]
k=2 idx = 4
back idx= 1 back i=3 k = 3
before idx= 1 before i=5 k = 2 ;before idx= 5 before i=6 k = 1 ;end
k=1 idx = 6
back idx= 5 back i=5 k = 2
end
k=2 idx = 5
back idx= 1 back i=4 k = 3
before idx= 1 before i=6 k = 2 ;end
k=2 idx = 6
back idx= 1 back i=5 k = 3
end
[3 2 1 ][4 2 1 ][5 2 1 ][4 3 1 ][5 3 1 ][5 4 1 ][4 3 2 ][5 3 2 ][5 4 2 ][5 4 3 ]
k=3 idx = 1