代码随想录day24打卡|| 93复原ip地址 78子集| 90子集||

93复原ip地址

力扣题目链接

题目描述

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "[email protected]" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

代码：

class Solution {  
public:  
    // 存放有效 IP 地址的结果集  
    vector<string> result;   

    // 回溯函数，参数为字符串 s，起始索引 startindex 和当前点的数量 pointNum  
    void backtracking(string &s, int startindex, int pointNum) {  
        // 当已经插入了三个点时，开始判断最后一个段是否有效  
        if (pointNum == 3) {  
            // 如果最后一段合法，则将当前字符串加入结果  
            if (islegle(s, startindex, s.size() - 1)) {  
                result.push_back(s);  
            }  
            return; // 结束当前回溯  
        }  

        // 遍历字符串中的字符，从 startindex 开始  
        for (int i = startindex; i < s.size(); i++) {  
            // 检查从 startindex 到当前位置 i 的段是否合法  
            if (islegle(s, startindex, i)) {  
                // 在 i 后面插入一个点  
                s.insert(s.begin() + i + 1, '.');  
                pointNum++; // 增加点的数量  

                // 继续递归调用 backtracking，移动起始索引到 i + 2（点的下一个字符）  
                backtracking(s, i + 2, pointNum);  

                pointNum--; // 回退点的数量  
                s.erase(s.begin() + i + 1); // 移除插入的点，回溯到上一个状态  
            } else {  
                break; // 如果该段不合法，结束当前循环  
            }        
        }  
    }  

    // 判断给定的段是否合法  
    bool islegle(string s, int start, int end) {  
        // 如果起始位置大于结束位置，返回 false  
        if (start > end) {  
            return false;  
        }  

        // 如果段以 '0' 开头，并且不是单个 '0'，返回 false  
        if (s[start] == '0' && start != end) {  
            return false;  
        }  

        int num = 0;   
        // 遍历该段的字符，验证每个字符  
        for (int i = start; i <= end; i++) {  
            // 验证是否为数字  
            if (s[i] > '9' || s[i] < '0') {  
                return false;  
            }  
            // 将字符转换为整数  
            num = num * 10 + (s[i] - '0');  
            // 如果数值大于 255，返回 false  
            if (num > 255) {  
                return false;  
            }  
        }  
        return true; // 如果所有检测都通过，返回 true  
    }  

    // 主函数，用于恢复所有有效的 IP 地址  
    vector<string> restoreIpAddresses(string s) {  
        backtracking(s, 0, 0); // 从字符串的开始位置和点的数量为 0 开始回溯  
        return result; // 返回结果集  
    }  
};  

78子集|

力扣题目链接

题目描述：

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的

子集

（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

代码：

class Solution {  
public:  
    // 存储最终结果的二维向量，保存所有可能的子集  
    vector<vector<int>> result;  
    
    // 存储当前路径的线性向量，用于构建子集  
    vector<int> path;  

    // 回溯函数，参数为数字数组 nums 和当前的起始索引 startindex  
    void backtracking(vector<int>& nums, int startindex) {  
        // 将当前路径（子集）添加到结果中  
        result.push_back(path);  

        // 从 startindex 开始遍历 nums  
        for (int i = startindex; i < nums.size(); i++) {  
            // 将当前元素添加到路径中  
            path.push_back(nums[i]);  
            // 递归调用，探索下一个元素（i + 1避免重复选择同一元素）  
            backtracking(nums, i + 1);  
            // 从路径中移除最后添加的元素以回溯，准备下一次选择  
            path.pop_back();  
        }  
    }  

    // 主函数，用于返回所有子集  
    vector<vector<int>> subsets(vector<int>& nums) {  
        // 从起始索引 0 开始回溯  
        backtracking(nums, 0);  
        // 返回结果，包含所有的子集  
        return result;  
    }  
};  

代码逻辑概述：

1. result:

   • 这是一个二维向量，用于存储所有生成的子集。每个子集被存储为 vector<int> 类型的一个元素。

2. path:

   • path 是一个一维向量，用来存放当前正在构建的子集。每次在回溯过程中，都会对这个路径进行修改。

3. backtracking:

   • 这个函数用于递归生成所有的子集。它接受两个参数：数字数组 nums 和当前的起始索引 startindex。
   • 添加当前子集：每次调用 backtracking 时，当前路径（作为子集）都会被添加到结果中。
   • 循环遍历：通过一个 for 循环来遍历输入数组 nums 中的每个元素，从 startindex 开始。对于每个元素：
     • 将其添加到 path 中，表示选取了这个元素。
     • 递归调用 backtracking，从 i + 1 开始进行下一轮的回溯，防止在同一层重复选择同一个元素。
     • 移除路径中的最后一个元素，以便回退到之前状态并尝试下一个可能的选择。

4. subsets:

   • 这是主函数，用于初始化回溯的过程。它从数组的起始位置（索引 0）调用 backtracking。最后返回存储所有子集的 result。

主要逻辑：

• 通过回溯生成子集：
  • 通过不断地在 path 中添加元素并递归调用，可以生成所有可能的组合（子集）。每当进入新的递归时，都将当前 path 状态保存，这样可以确保所有子集都会被记录。
  • 使用回溯（path.pop_back()）可以有效地恢复到先前状态，以便进行下一个元素的尝试。

90子集||

力扣题目链接

题目描述：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 

子集

（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

代码：

class Solution {  
public:  
    // 存储最终结果的二维向量，保存所有可能的子集  
    vector<vector<int>> result;  
    
    // 存储当前路径的线性向量，用于构建子集  
    vector<int> path;  

    // 回溯函数，参数为数字数组 nums 和当前的起始索引 startindex  
    void backtracking(vector<int>& nums, int startindex) {  
        // 将当前路径（子集）添加到结果中  
        result.push_back(path);   

        // 从 startindex 开始遍历 nums  
        for (int i = startindex; i < nums.size(); i++) {  
            // 跳过重复元素，确保结果中不出现重复的子集  
            if (i > startindex && nums[i] == nums[i - 1]) {  
                continue; // 如果当前元素与前一个元素相同，则跳过  
            }  
            // 将当前元素添加到路径中  
            path.push_back(nums[i]);  
            // 递归调用，探索下一个元素（i + 1 避免重复选择同一元素）  
            backtracking(nums, i + 1);  
            // 从路径中移除最后添加的元素以回溯，准备下一次选择  
            path.pop_back();  
        }  
    }  

    // 主函数，用于返回所有子集  
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {  
        // 首先对数组进行排序，以便于后续处理重复元素  
        sort(nums.begin(), nums.end());  
        // 从起始索引 0 开始回溯  
        backtracking(nums, 0);  
        // 返回结果，包含所有的子集  
        return result;   
    }  
};

代码逻辑概述：

1. result:

   • 这是一个二维向量，用于存储所有生成的子集。每个子集作为 vector<int> 类型的一个元素被保存。

2. path:

   • path 是一个一维向量，用于存放当前正在构建的子集。它在回溯的过程中被不断修改，以代表当前的子集状态。

3. backtracking:

   • 这个函数用于递归生成所有的子集。它接受两个参数：数字数组 nums 和当前的起始索引 startindex。
   • 保存当前子集：在每次调用 backtracking 时，当前路径（作为子集）都会被添加到结果中。
   • 循环遍历：通过一个 for 循环遍历输入数组 nums 中的每个元素，从 startindex 开始。对于每个元素：
     • 跳过重复项：使用 if (i > startindex && nums[i] == nums[i - 1]) 来检测是否当前元素与前一个元素相同。如果相同，则跳过此元素，以避免在结果中产生重复的子集。
     • 将当前元素添加到 path 中，表示选取了这个元素。
     • 递归调用 backtracking，并将起始索引移到 i + 1，这确保了不在同一层选择相同的元素。
     • 从路径中移除最后添加的元素，为会退回到之前的状态，以准备下一次选择。

4. subsetsWithDup:

   • 这是主函数，用于初始化回溯过程。首先，对输入数组进行排序，以便有效地处理后续可能的重复项（因排序后相同的元素将会相邻）。然后，从索引 0 开始调用 backtracking。最后返回存储所有子集的 result。

主要逻辑：

• 生成所有可能的子集：

  • 通过使用回溯的方法，不断地在 path 中添加元素并递归调用，可以生成所有的组合（子集）。每当进入新的递归时，都会保存当前的 path 状态以确保所有的子集都会被记录。

• 避免重复子集的关键：

  • 排序和跳过重复元素是避免重复子集的关键步骤。排序确保相同的元素是相邻的，而通过仅在第一次出现时选择这些元素，可以确保只生成一次包含这些元素的子集