代码随想录算法训练营第二十四天|leetcode78、90、93题

一、leetcode第93题

class Solution {
public:vector<string> restoreIpAddresses(string s) {int n = s.size();vector<string> res;function<void(string, int, int)> dfs = [&](string ss, int idx, int t) -> void {// 终止条件，枚举完，使用了4次`.`，需要删掉一个`.`if (idx == n || t == 4) {if (idx == n && t == 4) {ss.pop_back();res.push_back(ss);}return;}// 枚举位数，从idx下标开始i个位数for (int i = 1; i <= 3; ++ i) {if (i + idx > n) return;if (i != 1 && s[idx] == '0') return;if (i == 3 && stoi(s.substr(idx, 3)) > 255) return;dfs(ss + s.substr(idx, i) + ".", idx + i, t + 1);}};dfs("", 0, 0);return res;}
};

二、leetcode第78题

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己if (startIndex >= nums.size()) { // 终止条件可以不加return;}for (int i = startIndex; i < nums.size(); i++) {path.push_back(nums[i]);backtracking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtracking(nums, 0);return result;}
};

三、leetcode第90题

class Solution {vector<vector<int>> res;vector<int> path;//组合问题设置stratindex：为了防止重复//排列问题从0开始void dfs(vector<int>&nums,int startindex,vector<bool>&st){res.push_back(path);//先加入答案if(startindex>=nums.size()){return;}for(int i=startindex;i<nums.size();i++){//树层去重if(i>0&&nums[i-1]==nums[i]&&st[i-1]==false) continue;st[i]=true;path.push_back(nums[i]);dfs(nums,i+1,st);st[i]=false;path.pop_back();}}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {vector<bool> st(nums.size(),false);sort(nums.begin(),nums.end());dfs(nums,0,st);return res;}
};