算法打卡 Day29（回溯算法）-复原 IP 地址 + 子集 + 子集 Ⅱ

Leetcode 93-复原 IP 地址

题目描述

https://leetcode.cn/problems/restore-ip-addresses/description/

解题思路

这是一道切割问题，可以参考分割回文串的思路

采用 isValid 函数判断当前切割得到的子串是否有效

class Solution {
public:vector<string> res;bool isValid(string s, int start, int end){if(start > end) return false;if (s[start] == '0' && end - start > 0) return false;if (end - start + 1 > 3) return false; // 添加长度检查string sub = s.substr(start, end-start+1);int num = stoi(sub);if (num > 255) return false;return true;}void backTracking(string s, int startIndex, int dotNum){if(dotNum == 3){if (isValid(s, startIndex,s.size()-1)){res.push_back(s);}return;}for (int i = startIndex; i< startIndex+3 && i <s.size();i++){if (isValid(s, startIndex,i)){s.insert(s.begin()+i+1,'.');dotNum += 1;backTracking(s, i + 2, dotNum);dotNum -= 1;s.erase(s.begin()+i+1);}}}vector<string> restoreIpAddresses(string s) {backTracking(s,0,0);return res;}
};

Leetcode 78-子集

题目描述

https://leetcode.cn/problems/subsets/description/

解题思路

在子集问题中需要在每一层递归中进行结果的收集

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& nums, int count, int startIndex){if (path.size()==count) {res.push_back(path);return;}for (int i = startIndex; i <nums.size();i++){path.push_back(nums[i]);backTracking(nums,count, i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {for (int i =0; i <=nums.size(); i++){backTracking(nums,i,0);}return res;}
};

Leetcode 90-子集 Ⅱ

题目描述

https://leetcode.cn/problems/subsets-ii/description/

解题思路

class Solution {
public:vector<vector<int>> res;vector<int> path;void backTracking(vector<int>& nums, int startIndex){res.push_back(path);if (startIndex == nums.size()) return;for (int i =startIndex; i < nums.size();i++){if (i >startIndex && 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;}
};