21.回溯算法3

复原ip地址 class Solution { public: string ip; vector<string> res; int level=0; void backtracking(string s,int start){ if((level==4)&&(start==s.size())){ res.push_back(ip.erase(ip.size()-1,1)); return; }else if((level<4)&&(start>s.size())){ return; } int sum=0; for(int i=start;i<s.size();i++){ if(i==start+1&&s[start]=='0')return;; sum=sum*10+(s[i]-'0'); ip+=s[i]; if(sum>=0&&sum<=255){ string tmp=ip; ip+="."; level++; backtracking(s,i+1); level--; ip=tmp; }else{return;} } } vector<string> restoreIpAddresses(string s) { backtracking(s,0); return res; } };

The error you’re encountering is due to an incorrect operation in the line:

ip += s[i] + ".";

Here, s[i] is a character, and when you add it to the string ".", it doesn’t behave as expected. Instead of appending the character followed by a dot (.), the expression s[i] + "." tries to perform pointer arithmetic because s[i] is treated as an integer (its ASCII value) and "." is treated as a const char*. This leads to undefined behavior, which is causing the runtime error.

所以要分成两步写,当然正确的逻辑是不会写出这句的，因为+s[i]是在循环外面，我是写错的时候发现了这个错误，所以记录一下。

子集 class Solution { public: vector<vector<int>> res; void recursive(vector<int>& nums,int start){ if(start==nums.size()){ vector<int> tmp; res.push_back(tmp); return; } recursive(nums,start+1); int n=res.size(); for(int i=0;i<n;i++){ vector<int> tmp; tmp=res[i]; tmp.push_back(nums[start]); res.push_back(tmp); } } vector<vector<int>> subsets(vector<int>& nums) { recursive(nums,0); return res; } }; 子集2 class Solution { public: vector<int> path; vector<vector<int>> res; void backtracking(vector<int>& nums,int start){ for(int i=start;i<nums.size();i++){ if(i>start&&nums[i-1]==nums[i])continue; path.push_back(nums[i]); backtracking(nums,i+1); path.pop_back(); } res.push_back(path); } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); backtracking(nums,0); return res; } };