day28|93. 复原 IP 地址|Leetcode 78. 子集|90.子集II

Leetcode 93. 复原 IP 地址

链接：93. 复原 IP 地址

class Solution {
public:vector<string> res;string path;int pointNum = 0;vector<string> restoreIpAddresses(string s) {backtracking(0, s);return res;}void backtracking(int start, string s) {if (pointNum == 3) {string cur = s.substr(start);if (isValid(cur)) {res.push_back(path + cur);}return;}for (int i = start; i < s.length(); i++) {string cur = s.substr(start, i - start + 1);if (isValid(cur)) {int len = path.length();path += cur + ".";pointNum++;backtracking(i + 1, s);path = path.substr(0, len);pointNum--;} else {break;}}}bool isValid(string str) {if (str.empty() || str.length() > 3 || (str[0] == '0' && str.length() > 1))return false;int num = stoi(str);return num >= 0 && num <= 255;}
};

Leetcode 78. 子集

链接：78. 子集

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

Leetcode 90.子集II

链接：90.子集II

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {result.push_back(path);for (int i = startIndex; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}path.push_back(nums[i]);used[i] = true;backtracking(nums, i + 1, used);used[i] = false;path.pop_back();}}public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end()); backtracking(nums, 0, used);return result;}
};