93. 复原 IP 地址
1.当点号有三个之后，当最后一部分数值是有效的话， 就可以加入结果集了
class Solution {
public:vector<string> res;bool isvalid(const string& s, int left, int right){if (right < left){return false;}if (s[left] == '0' and right-left>0){// 0开头的数字不合法return false;}int su = 0;for(int i = left; i <= right; i++){su = su * 10 + (s[i] - '0');if (su > 255){// 如果大于255了不合法return false;}} return true;}void backtracking(string s, int point_num, int s_index){if (point_num == 3){ if (isvalid(s, s_index, s.size()-1))res.push_back(s);return;}for(int i = s_index; i < s.size(); i++){if (isvalid(s,s_index,i)){s.insert(s.begin() + i + 1, '.');// 在i的后面插入一个逗点point_num++; backtracking(s, point_num, i+2);// 插入逗点之后下一个子串的起始位置为i+2point_num--;s.erase(s.begin()+i+1);}else{break;}}}vector<string> restoreIpAddresses(string s) {backtracking(s, 0, 0);return res;}
};78. 子集
这一题确实就是动态规划的模板，一开始我还考虑了如何停止，后来发现不用，因为start_index在逐次上升，自然就会停止，直接收集结果就可以；
因为是直接push_back(path)，连path是[]的情况也包含了，不需要额外处理；
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int start_index){if (start_index>= nums.size()) { // 终止条件可以不加return;}res.push_back(path);for(int i = start_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
- 这一题是上一题的延申，基础写法延续上一题；
- 去重的方法之前也学习过，使用used，要点是(i > 0 and used[i-1] == 0 and nums[i] == nums[i-1])，num[i]没用过，但是num[i]又和num[i-1]的值相同;
- 这里需要注意一下used的初始化方法，许久没用，又给忘了,vector<int> used(nums.size(), 0); //初始长度为num的长度，值为0
- 注意，需要排序
class Solution {
public:vector<vector<int>> res;vector<int> path;void backtracking(vector<int>& nums, int start_index, vector<int>& used){res.push_back(path);for(int i = start_index; i < nums.size(); i++){if (i > 0 and used[i-1] == 0 and nums[i] == nums[i-1]){continue;}path.push_back(nums[i]);used[i] = 1;backtracking(nums, i+1, used);used[i] = 0;path.pop_back();}}vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end());vector<int> used(nums.size(), 0); backtracking(nums, 0, used);return res;}
};
