代码随想录训练营Day20 | 93.复原IP地址 - 78.子集 - 90.子集II

93.复原IP地址

• 题目链接：93.复原IP地址
• 思路：
  1. 做法和分割回文字符串那题类似，是对字符串进行切割；
  2. 本题需要多几个条件，就是每次回溯字符串的长度最多三位，字符串对应的数值必须 在[0, 255]之间，并且不能有前导0的存在，并且只能被切割成4个字符串
• 代码：

class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> ans;vector<string> tmp;if(s.size() > 12) // 字符串长度最大为12return {};int n = s.size();auto dfs = [&](auto&& dfs, int k) {if(k < n && tmp.size() == 4) // 切割了四个数，但是字符串还剩下，不符合return;if(k == n && tmp.size() == 4) { // 符合条件stringstream ss; // 将字符串数组转化为ip地址for(int i = 0; i < 4; ++i) {ss << tmp[i];if(i != 3) ss << '.';}  ans.push_back(ss.str());}string str = "";for(int i = k; i < n && i < k + 3; ++i) {str += s[i];if(stoi(str) <= 255) { // 在[0. 255]之前tmp.push_back(str);dfs(dfs, i+1);tmp.pop_back();}if(s[k] == '0')   // 去除前导0break;}};dfs(dfs, 0);return ans;}
};

78.子集

• 题目链接：78.子集
• 思路：本题较为简单，每次一个数没有被选择的数，即可组成一个集合，将集合放入到答案中即可
• 代码：

class Solution {
public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;int n = nums.size();auto dfs = [&](auto&& dfs, int i) {ans.push_back(tmp); // 记录集合if(i == n) {return;}for(int j = i; j < n; j++) {tmp.push_back(nums[j]); // 选一个数dfs(dfs, j+1);tmp.pop_back();}};dfs(dfs, 0);return ans;}
};

90.子集II

• 题目链接：90.子集II
• 思路：思路和子集那道题一样，不同的是这道题需要进行去重，相同数字，在一次回溯函数过程中只能被选择一次，需要进行去重，所以需要先排序
• 代码：

class Solution {
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;ranges::sort(nums);  // 数组排序，方便去重int n = nums.size();auto dfs = [&](auto&& dfs, int i) {ans.push_back(tmp);if(i == n) {return;}for(int j = i; j < n; j++) {if(j != i && nums[j] == nums[j-1]) // 去重continue;tmp.push_back(nums[j]);dfs(dfs, j+1);tmp.pop_back();}};dfs(dfs, 0);return ans;}
};