完全背包|dfs

lc93

复原ip

 方法思路
 
1. 深度优先搜索（DFS）：通过递归的方式枚举所有可能的 IP 地址分割点。
2. 有效部分检查：每次递归时，检查当前分割的部分是否为有效整数（在 0 到 255 之间，且无rike前导零）。
3. 递归终止条件：当已经插入了 3 个  .  且处理完整个字符串时，将当前路径加入结果集。
 
解决代码
 
class Solution {
    string s;
    vector<string> ret;
    string path;
    int cnt = 0, n = 0;
public:
    vector<string> restoreIpAddresses(string s) {
        this->s = s;
        n = s.size();
        dfs(0);
        return ret;
    }
    void dfs(int p) {
        if (p == n && cnt == 3) {
            ret.push_back(path);
            return;
        }
        if (cnt > 3) {
            return;
        }
        if (p >= n) {
            return;
        }
        if (s[p] == '0') {
            if (path.empty()) {
                path = "0";
            } else {
                path += ".0";
            }
            cnt++;
            dfs(p + 1);
            if (path.empty()) {
                path = "";
            } else {
                path = path.substr(0, path.size() - 2);
            }
            cnt--;
            return;
        }
        int num = 0;
        for (int i = p; i < n; i++) {
            num = num * 10 + (s[i] - '0');
            if (num > 255) {
                break;
            }
            string temp = path;
            if (path.empty()) {
                path = to_string(num);
            } else {
                path += "." + to_string(num);
            }
            cnt++;
            dfs(i + 1);
            path = temp;
            cnt--;
        }
    }
};
 
 
代码解释
 
1. 类成员变量：
-  s ：存储输入的数字字符串。
-  ret ：存储所有有效的 IP 地址结果。
-  path ：当前正在构建的 IP 地址。
-  cnt ：记录已插入的  .  数量。
-  n ：输入字符串的长度。
2.  restoreIpAddresses  方法：
- 初始化类成员变量，调用  dfs  方法开始递归搜索。

3.  dfs  方法：
- 终止条件：当处理完整个字符串且已插入 3 个  .  时，将当前路径加入结果集。
- 剪枝条件：如果已插入的  .  数量超过 3 或已处理完字符串但  .  数量不足 3，直接返回。
- 处理前导零：如果当前字符是  0 ，单独处理（因为前导零无效，只能作为单独的部分）。
- 枚举分割点：遍历当前位置到字符串末尾，计算当前分割部分的数值，检查是否在 0 到 255 之间，符合条件则递归处理剩余部分，并在递归后回溯状态。
 
dfs枚举所有可能的分割方式，并在每一步检查分割部分的有效性，确保最终得到的 IP 地址是有效的。

lc47.全排列ii

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<bool> check;

    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        //排序
        sort(nums.begin(),nums.end());
        check.resize(nums.size(),false); //init

        dfs(nums);
        return ret;
    }

    void dfs(vector<int>& nums)
    {
        if(path.size()==nums.size())//end
        {
            ret.push_back(path);
            return;
        }

        for(int i=0;i<nums.size();i++)//遍历所有元素
        {
    //legal
            if(check[i]==false && (i==0 || nums[i]!=nums[i-1] || check[i-1]==true))
        {
            check[i]=true;
            path.push_back(nums[i]);

            dfs(nums);

            check[i]=false;//还原
            path.pop_back();

       }   
            
      }
    }
};

lc39

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ranges::sort(candidates);
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left) {
            if (left == 0) {
                // 找到一个合法组合
                ans.push_back(path);
                return;
            }

            // 枚举选哪个
            for (int j = i; j < candidates.size() && candidates[j] <= left; j++) {
                path.push_back(candidates[j]);
                dfs(j, left - candidates[j]);

                path.pop_back(); // 恢复现场
            }
        };

        dfs(0, target);
        return ans;
    }
};