day24 回溯3
93.復(fù)原IP地址
class Solution {
public:
vector<string> res;
string path;
bool isValid(string s) {
if (s.size() > 3 || (s.size() > 1 && s[0] == '0')) {
return false;
}
if (stoi(s) > 255) {
return false;
}
return true;
}
void backtracking(const string &s, int index) {
if (index >= s.size() && path.size() == s.size() + 4) {
res.push_back(path.substr(0, path.size() - 1));
return;
}
for (int i = index; i < s.size(); i ++) {
string str = s.substr(index, i - index + 1);
if (isValid(str)) {
path += str + ".";
int n = str.size() + 1;
backtracking(s, i + 1);
while (n --) {
path.pop_back();
}
}
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0);
return res;
}
};
78.子集
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int> &nums, int index) {
res.push_back(path);
if (index >= nums.size()) {
return;
}
for (int i = index; i < nums.size(); i ++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
90.子集II
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void backtracking(vector<int> &nums, int index) {
res.push_back(path);
if (index >= nums.size()) {
return;
}
for (int i = index; i < nums.size(); i ++) {
if (i > index && nums[i] == nums[i-1]) {
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 res;
}
};
