Restoring Valid IPv4 Addresses

Generating all possible valid IP address strings from a numeric sequence requires dividing the input into four segments where each part falls between 0 and 255. Leading zeros are not permitted unless the segment is exactly "0". A backtracking approach iterates through potential split points, validating segments before recursing deeper.

To optimize state management, we maintain a list of valid segments rather than mutating string objects repeatedly during recursion.

import java.util.ArrayList;
import java.util.List;

class Ipv4Solver {
    private List<String> foundAddresses = new ArrayList<>();

    public List<String> findIpStrings(String digits) {
        if (digits.length() < 4 || digits.length() > 12) {
            return foundAddresses;
        }
        backtrack(digits, 0, 0, new ArrayList<>());
        return foundAddresses;
    }

    private void backtrack(String source, int currentIndex, int segmentCount, List<String> currentSegments) {
        // Base case: All segments selected
        if (segmentCount == 3) {
            int remainingLength = source.length() - currentIndex;
            if (remainingLength >= 1 && remainingLength <= 3) {
                String lastPart = source.substring(currentIndex);
                if (isValidSegment(lastPart)) {
                    currentSegments.add(lastPart);
                    foundAddresses.add(String.join(".", currentSegments));
                    currentSegments.remove(currentSegments.size() - 1);
                }
            }
            return;
        }

        // Try split lengths of 1 to 3 for next segment
        for (int length = 1; length <= 3 && currentIndex + length <= source.length(); length++) {
            String segment = source.substring(currentIndex, currentIndex + length);
            if (isValidSegment(segment)) {
                currentSegments.add(segment);
                backtrack(source, currentIndex + length, segmentCount + 1, currentSegments);
                currentSegments.remove(currentSegments.size() - 1);
            } else {
                break;
            }
        }
    }

    private boolean isValidSegment(String part) {
        if (part.isEmpty()) return false;
        if (part.startsWith("0") && part.length() > 1) return false;
        try {
            int value = Integer.parseInt(part);
            return value >= 0 && value <= 255;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

Generating Power Sets

Creating every comibnation of elements from an array is a classic application of tree-based depth-first search. At each index, there are two choices: include the element or skip it. However, iterating through indices while building subsets simplifies the logic by avoiding nested choice loops.

We add the current path to the result collection at the start of every recursive call to capture subsets of different sizes.

import java.util.ArrayList;
import java.util.List;

class PowerSetGenerator {
    private List<List<Integer>> outputSets = new ArrayList<>();
    private List<Integer> activeSubset = new ArrayList<>();

    public List<List<Integer>> getAllCombinations(int[] numbers) {
        generateSubsets(numbers, 0);
        return outputSets;
    }

    private void generateSubsets(int[] nums, int startNode) {
        // Save snapshot of current configuration
        outputSets.add(new ArrayList<>(activeSubset));

        for (int i = startNode; i < nums.length; i++) {
            activeSubset.add(nums[i]);
            generateSubsets(nums, i + 1);
            activeSubset.remove(activeSubset.size() - 1); // Backtrack
        }
    }
}

Handling Duplicate Elements in Subsets

When the input array contains duplicate integers, naive subset generation produces redundant results. To filter these duplicates, we must sort the input first. Then, during iteration, we skip an element if it is identical to the previous element and that previous element was not used in the current recursion level.

This ensures that with in the same tree layer, identical numbers are only picked once, preventing combinatorial duplication.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class UniqueSubsets {
    private List<List<Integer>> uniqueResults = new ArrayList<>();
    private List<Integer> currentCombo = new ArrayList<>();
    private boolean[] isSelected;

    public List<List<Integer>> distinctSubsets(int[] data) {
        Arrays.sort(data);
        isSelected = new boolean[data.length];
        traverse(data, 0);
        return uniqueResults;
    }

    private void traverse(int[] nums, int startIdx) {
        uniqueResults.add(new ArrayList<>(currentCombo));

        for (int k = startIdx; k < nums.length; k++) {
            if (k > 0 && nums[k] == nums[k - 1] && !isSelected[k - 1]) {
                continue;
            }

            isSelected[k] = true;
            currentCombo.add(nums[k]);
            traverse(nums, k + 1);
            currentCombo.remove(currentCombo.size() - 1);
            isSelected[k] = false;
        }
    }
}