阶段性还完了旧账
复原IP地址
leetcode：93. 复原 IP 地址
回溯法
思路
和分割回文串类似，只是回文串检测改为IP合法检测。
终止条件也值得注意：
复杂度分析
时间复杂度：
空间复杂度：
注意点
代码实现
递归不一定要返回！！
class Solution {
private:
vector<string> result;
vector<string> path;
public:
void backtracking(string& s,int begin){
// 分成四份的时候就及时处理，符合的就直接加入，若不符合就返回
if(path.size() == 4){
// begin == s.size()表示遍历完,可以放入结果集
if(begin == s.size()){
string str;
for(int i = 0;i < path.size() - 1;i++){
str += path[i]; str += '.';
}
str += path[path.size() - 1];
result.push_back(str);
}
return;
}
for(int i = begin;i < s.size();i++){
if(i - begin + 1 > 3) return; // 剪枝,如果剩余子串长度超过3就退出
if(isValid(s,begin,i)){ // 如果字串合法,则放入path数组
path.push_back(s.substr(begin,i - begin + 1));
backtracking(s,i + 1);
path.pop_back();
}
}
}
// 左闭右闭
bool isValid(string& s, int begin, int end) {
// 长度大于1且开头为0,去掉. 排除0开头的多位数
if (end - begin + 1 > 1 && s[begin] == '0') return false;
int sum = 0;
for (int i = begin; i <= end; i++) {
sum = sum * 10 + (s[i] - '0');
if (sum > 255) return false;
}
return true;
}
vector<string> restoreIpAddresses(string s) {
backtracking(s,0);
return result;
}
};
子集
leetcode：78. 子集
回溯法
思路
和组合一样，不过树的每个节点都是解，都放入结果集。
复杂度分析
时间复杂度：O(2N*N)。遍历所有的结果是O(2N)，将path复制进result的时间是O(N)（子集平均长度2/N）。
空间复杂度：O(N)。
注意点
- 空集也是所有子集里的一个。（我这里其实没有想到，阴差阳错地刚好满足了）
- 我这里才意识到：递归不一定要有return的，只要不是无限循环，执行完了自动会返回上一层。
代码实现
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
// 类组合，树上每个节点都是解。
void backtracking(vector<int>& nums,int begin){
result.push_back(path);
for(int i = begin;i < nums.size();i++){ // for暗含终止条件
path.push_back(nums[i]);
backtracking(nums,i + 1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};
子集Ⅱ
leetcode：90. 子集 II
回溯法
思路
依旧是组合，放入每个节点，不过要去重。
先排序，然后进行树层去重（同一层，值一样的元素跳过）
复杂度分析
时间复杂度：O(2^N*N)。虽有去重，但数量级没变。
空间复杂度：
注意点
- 树层去重时的条件是
i > begin而不是i > 0。因为要控制在同层子集范围内比较（begin~i），否则就不是同父节点的同一层了。
代码实现
使用begin下标版：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
// 组合，放入每个节点，并且要去重
// 先排序，然后进行树层去重（同一层，值一样的元素跳过）
void backtracking(vector<int>& nums,int begin){
result.push_back(path);
for(int i = begin;i < nums.size();i++){
// i > begin是因为要控制在同层子集范围内比较，否则就不是同父节点的同一层了。
if(i > begin && nums[i - 1] == nums[i]) continue; // 同层同值元素跳过
path.push_back(nums[i]);
backtracking(nums,i + 1);
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
backtracking(nums,0);
return result;
}
};
使用used数组版：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
public:
// 组合，放入每个节点，并且要去重
// 先排序，然后进行树层去重（同一层，值一样的元素跳过）
void backtracking(vector<int>& nums,int begin,vector<bool> used){
result.push_back(path);
for(int i = begin;i < nums.size();i++){
if(i > 0 && nums[i - 1] == nums[i] && used[i-1] == false) continue; // 同层同值元素跳过
path.push_back(nums[i]);
used[i] = true;
backtracking(nums,i + 1,used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(),false);
backtracking(nums,0,used);
return result;
}
};