Restauração de Endereços IP

O desafio de restaurar endereços IP consiste em inserir pontos em uma string de dígitos de forma que os segmentos resultantes constituam um endereço IPv4 válido. Cada segmento deve estar entre 0 e 255 e não pode conter zeros à esquerda, a menos que seja o próprio zero.

A solução utiliza uma abordagem recursiva (backtracking) para explorar todas as posições possíveis para inserir os pontos. Implementamos uma função auxiliar para verificar a validade de cada segmento antes de prosseguir para a próxima profundidade da recursão.

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        valid_ips = []
        self._search_ips(s, 0, 0, [], valid_ips)
        return valid_ips

    def _is_valid_segment(self, segment: str) -> bool:
        # Verifica se o segmento é vazio ou tem zero à esquerda (exceto "0")
        if not segment or (len(segment) > 1 and segment[0] == '0'):
            return False
        # Verifica se o valor numérico está no intervalo [0, 255]
        return 0 <= int(segment) <= 255

    def _search_ips(self, s: str, start_idx: int, parts_count: int, current_parts: list, results: list):
        # Se já temos 4 partes, verificamos se usamos toda a string
        if parts_count == 4:
            if start_idx == len(s):
                results.append(".".join(current_parts))
            return
        
        # Tenta segmentos de tamanho 1, 2 e 3
        for length in range(1, 4):
            if start_idx + length > len(s):
                break
            
            candidate = s[start_idx : start_idx + length]
            if self._is_valid_segment(candidate):
                current_parts.append(candidate)
                self._search_ips(s, start_idx + length, parts_count + 1, current_parts, results)
                current_parts.pop() # Backtracking

Subconjuntos (Subsets)

Este problema clássico solicita a geração de todos os subconjuntos possíveis (o conjunto potência) de uma lista de inteiros distintos. Diferente de problemas de combinação onde coletamos resultados apenas nos nós folha da árvore de recursão, aqui coletamos o estado atual em cada nó visitado.

O algoritmo itera sobre a lista de entrada, incluindo cada elemento no caminho atual e recursivamente buscando subconjuntos que começam a partir do próximo índice.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        all_subsets = []
        self._build_subsets(nums, 0, [], all_subsets)
        return all_subsets

    def _build_subsets(self, nums: List[int], start: int, path: List[int], results: List[List[int]]):
        # Adiciona uma cópia do caminho atual aos resultados
        results.append(path.copy())
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            # Avança para i + 1 para evitar reutilizar o mesmo elemento
            self._build_subsets(nums, i + 1, path, results)
            path.pop() # Remove o elemento para tentar o próximo candidato

Subconjuntos II (Subsets II)

Uma variação do problema anterior onde a lista de entrada pode conter números duplicados. O objetivo é gerar todos os subconjuntos únicos, evitando combinações duplicadas no resultado final.

A estratégia envolve ordenar o array inicialmente. Durante a recursão, se encontrarmos um elemento que é igual ao anterior e o anterior não foi incluído no caminho atual (indicando que estamos no mesmo nível da árvore de recursão), pulamos esse elemento para evitar duplicatas.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort() # Ordenação é crucial para identificar duplicatas adjacentes
        unique_subsets = []
        self._build_unique_subsets(nums, 0, [], unique_subsets)
        return unique_subsets

    def _build_unique_subsets(self, nums: List[int], start: int, path: List[int], results: List[List[int]]):
        results.append(path.copy())
        
        for i in range(start, len(nums)):
            # Se o número atual é igual ao anterior e o anterior não está no path atual,
            # significa que estamos em um nível de repetição. Devemos pular.
            if i > start and nums[i] == nums[i-1]:
                continue
            
            path.append(nums[i])
            self._build_unique_subsets(nums, i + 1, path, results)
            path.pop()