Restoring IP Addresses from String

Given a string containing only digits, generate all possible valid IP address combinations. A valid IP address consists of four integers separated by dots, each integer ranging from 0 to 255, without leading zeros except for the number zero itself.

Approach

The problem is a variant of the partitioning problem, which can be solved using backtracking. The key steps are:

1. Recursive Function Parameters: Track the current index in the string and the count of dots placed.
2. Termination Condition: When three dots have been placed, check if the remaining substring forms a valid segment. If so, add the complete IP to the results.
3. Recursive Logic: For each segment starting at the current index, check validity. If valid, place a dot and recurse on the next segment. Backtrack by removing the dot.

Validity Check

A segment is valid if:

• It does not have leading zeros unless its exact "0".
• Its integer value is between 0 and 255.

Implementation

#include <vector>
#include <string>
using namespace std;

class Solution {
    vector<string> output;
    void backtrack(string s, int idx, int dots) {
        if (dots == 3) {
            if (isValid(s, idx, s.length() - 1)) {
                output.push_back(s);
            }
            return;
        }
        for (int j = idx; j < s.length(); j++) {
            if (isValid(s, idx, j)) {
                s.insert(j + 1, ".");
                backtrack(s, j + 2, dots + 1);
                s.erase(j + 1, 1);
            } else {
                break;
            }
        }
    }
    bool isValid(const string& str, int left, int right) {
        if (left > right) return false;
        if (str[left] == '0' && left != right) return false;
        int num = 0;
        for (int k = left; k <= right; k++) {
            if (str[k] < '0' || str[k] > '9') return false;
            num = num * 10 + (str[k] - '0');
            if (num > 255) return false;
        }
        return true;
    }
public:
    vector<string> restoreIpAddresses(string s) {
        output.clear();
        if (s.length() < 4 || s.length() > 12) return output;
        backtrack(s, 0, 0);
        return output;
    }
};

Generating All Subsets

Given a set of distinct integers, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Approach

The subset problem can be visualized as a tree where each node represents a decision to include or exclude an element. The backtracking algorithm collects all nodes (subsets) in the tree.

1. Recursive Function Parameters: Track the starting index to avoid reusing elements.
2. Termination Condition: When the start index exceeds the array bounds, return (though not strictly necessary as the loop won't execute).
3. Recursive Logic: At each step, add the current element to the subset, recurse on the next index, then backtrack by removing the element. Collect the current subset at every step.

Implementation

#include <vector>
using namespace std;

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

Generating Subsets with Duplicates

Given a collection of integers that might contain duplicates, return all possible subsets without duplicate subsets.

Approach

Similar to the distinct subsets problem, but requires avoiding duplicate subsets. First, sort the array. During backtracking, skip over duplicate elements at the same level (tree level) to prevent duplicate subsets.

Implementation Using Usage Tracking

#include <vector>
#include <algorithm>
using namespace std;

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

Implementation Using Set for Level Uniqueness

#include <vector>
#include <algorithm>
#include <unordered_set>
using namespace std;

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void backtrack(vector<int>& nums, int start) {
        res.push_back(path);
        unordered_set<int> seen;
        for (int i = start; i < nums.size(); i++) {
            if (seen.find(nums[i]) != seen.end()) continue;
            seen.insert(nums[i]);
            path.push_back(nums[i]);
            backtrack(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        res.clear();
        path.clear();
        sort(nums.begin(), nums.end());
        backtrack(nums, 0);
        return res;
    }
};