93. 复原 IP 地址
题目地址：93. 复原 IP 地址 - 力扣（LeetCode）
题解思路：回溯
时间复杂度：O(3^4)，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式
空间复杂度：O(n)
代码:
class Solution {
public:vector<string>ret;bool isValid(string& str, int start, int end){if(end < start){return false;}if(str[start] == '0' && start != end){return false;}int num = 0;for(int i = start; i <= end; i++){num = 10 * num + (str[i] - '0');if(num > 255){return false;}}return true;}void backtrack(string& s, int start, int point){// 只能有三个小数点if(point == 3){if(isValid(s, start, s.size() - 1)){ret.push_back(s);}return ;}int size = s.size();for(int i = start; i < size; i++){if(isValid(s, start, i)){s.insert(s.begin() + i + 1, '.'); // 插入小数点point++;backtrack(s, i + 2, point);point--;s.erase(s.begin() + i + 1);} else {break;}}}vector<string> restoreIpAddresses(string s) {// 剪枝if(s.size() < 4 || s.size() > 12) return ret;backtrack(s, 0, 0);return ret;}
};
78. 子集
题目地址：78. 子集 - 力扣（LeetCode）
题解思路：找子集问题
时间复杂度：O(n * 2n)，n个数，每个数考虑选or不选（2n）
空间复杂度：O(n)
代码:
class Solution {
public:vector<vector<int>>ret;vector<int>v;void backtrack(vector<int>&nums, int start){ret.push_back(v); // 子集if(start >= nums.size()){return ;}int size = nums.size();for(int i = start; i < size; i++){v.push_back(nums[i]);backtrack(nums, i + 1);v.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {// 子集问题，找到所有节点集合backtrack(nums, 0);return ret;}
};
