93. Restore IP Addresses

This problem requires partitioning a string into all possible valid IPv4 addresses. A valid IPv4 address consists of four decimal segments separated by dots, where each segment is an integer in the range [0, 255] and does not have leading zeros unless the segment is exactly "0".

The approach uses backtracking to explore all valid segmentations. At each recursive step, we try to extract a segment of length 1 to 3 starting from the current index. Only when the segment represents a valid number (≤ 255 and no leading zeros) do we proceed deeper. Special pruning occurs when the current segment is "0", because any further extension (e.g., "01", "012") is invalid — thus we terminate that branch immediately after processing "0".

A key optimization is early termination: if we already have 4 segments but haven't consumed the entire string, or if we still need more than the remaining characters can provide, we backtrack promptly.

<div>
class RestoreIPAddresses:
    def restoreIpAddresses(self, s: str) -> List[str]:
        result = []
        path = []

        def backtrack(start: int):
            if len(path) == 4:
                if start == len(s):
                    result.append(".".join(path))
                return

            for length in range(1, 4):
                if start + length > len(s):
                    break
                segment = s[start:start + length]
                if (segment[0] == '0' and len(segment) > 1) or int(segment) > 255:
                    continue
                path.append(segment)
                backtrack(start + length)
                path.pop()

        backtrack(0)
        return result
</div>

78. Subsets

This classic combinatorial problem asks to generate all possible subsets (the power set) of a given array of unique integers. Each element has two choices: either included or excluded. This naturally maps to a binary decision tree of depth n (where n is the array length), and depth-first搜索 explores all 2n paths.

Backtracking is applied by making a choice (include or exclude), recursing, and then undoing the choice. No handling for duplicates is required since all elements are distinct.

<div>
class Subsets:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []

        def dfs(index: int):
            if index == len(nums):
                result.append(path.copy())
                return
            # Exclude nums[index]
            dfs(index + 1)
            # Include nums[index]
            path.append(nums[index])
            dfs(index + 1)
            path.pop()

        dfs(0)
        return result
</div>

90. Subsets II

This variant includes duplicates in the input array. To avoid duplicate subsets, we first sort the array. During backtracking, when skipping a element, we must skip all its duplicates to prevent identical branches — otherwise, choosing index i and then skipping duplicates later would generate the same subset as skipping index i but including the next duplicate.

For example, with [1, 1, 2], after considering subsets that include the first 1, when we backtrack and skip the first 1, we must also skip the second 1 to avoid repetition. Thus, after backtracking the "include" branch, we increment the index past all identical values before the "exclude" recursive call.

<div>
class SubsetsII:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        path = []

        def dfs(index: int):
            if index == len(nums):
                result.append(path.copy())
                return

            # Include current element
            path.append(nums[index])
            dfs(index + 1)
            path.pop()

            # Skip all duplicates of current element
            j = index + 1
            while j < len(nums) and nums[j] == nums[index]:
                j += 1
            dfs(j)

        dfs(0)
        return result
</div>