Valid IP Address Generation

Given a string containing only digits, geenrate all possbile valid IP address combinations. A valid IP address consists of four integers between 0-255 separated by dots, with no leading zeros.

class IPGenerator {
    vector<string> validIPs;
    
    bool isValidSegment(const string& s, int start, int end) {
        if (start > end || end - start + 1 > 3) return false;
        if (s[start] == '0' && start != end) return false;
        
        int value = 0;
        for (int i = start; i <= end; i++) {
            if (!isdigit(s[i])) return false;
            value = value * 10 + (s[i] - '0');
            if (value > 255) return false;
        }
        return true;
    }
    
    void generate(string& s, int pos, int segments, string current) {
        if (segments == 4 && pos == s.length()) {
            validIPs.push_back(current);
            return;
        }
        
        for (int len = 1; len <= 3 && pos + len <= s.length(); len++) {
            if (isValidSegment(s, pos, pos + len - 1)) {
                string segment = s.substr(pos, len);
                string newCurrent = current.empty() ? segment : current + "." + segment;
                generate(s, pos + len, segments + 1, newCurrent);
            }
        }
    }
    
public:
    vector<string> restoreIPs(string s) {
        if (s.length() < 4 || s.length() > 12) return {};
        generate(s, 0, 0, "");
        return validIPs;
    }
};

Finding All Subsets

Given a set of distinct integers, return all possible subsets (the power set).

class SubsetFinder {
    vector<vector<int>> allSubsets;
    
    void find(vector<int>& nums, int index, vector<int>& current) {
        allSubsets.push_back(current);
        
        for (int i = index; i < nums.size(); i++) {
            current.push_back(nums[i]);
            find(nums, i + 1, current);
            current.pop_back();
        }
    }
    
public:
    vector<vector<int>> getSubsets(vector<int>& nums) {
        vector<int> current;
        find(nums, 0, current);
        return allSubsets;
    }
};

Handling Duplicate Elements in Subsets

When the input contains duplicates, we need to avoid duplicate subsets in the output.

class UniqueSubsetFinder {
    vector<vector<int>> uniqueSubsets;
    
    void findUnique(vector<int>& nums, int index, vector<int>& current) {
        uniqueSubsets.push_back(current);
        
        for (int i = index; i < nums.size(); i++) {
            if (i > index && nums[i] == nums[i-1]) continue;
            current.push_back(nums[i]);
            findUnique(nums, i + 1, current);
            current.pop_back();
        }
    }
    
public:
    vector<vector<int>> getUniqueSubsets(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> current;
        findUnique(nums, 0, current);
        return uniqueSubsets;
    }
};