Três problemas clássicos resolvidos com backtracking: validação de endereços IP, geração de subconjuntos (com e sem elementos repetidos). Abaixo estão as abordagens e os códigos refatorados.

93. Restaurar Endereços IP

Dada uma string contendo apenas dígitos, devem ser inseridos pontos para formar endereços IP válidos (quatro números de 0 a 255, sem zeros à esquerda, exceto para o próprio zero).

Estratégia: backtracking com construção incremental da string final. A cada passo, testa-se um segmento de 1 a 3 caracteres; se válido, insere-se um ponto e recursivamente processa-se o restante. Quando três pontos são inseridos, verifica-se o último segmento.

class SolucaoIP {
    List<String> enderecosValidos = new ArrayList<>();

    public List<String> restaurarIp(String s) {
        if (s.length() > 12) return enderecosValidos;
        construir(new StringBuilder(s), 0, 0);
        return enderecosValidos;
    }

    private void construir(StringBuilder atual, int inicio, int pontos) {
        if (pontos == 3) {
            String ultimo = atual.substring(inicio);
            if (segmentoValido(ultimo)) {
                enderecosValidos.add(atual.toString());
            }
            return;
        }
        for (int fim = inicio + 1; fim <= Math.min(inicio + 3, atual.length()); fim++) {
            String seg = atual.substring(inicio, fim);
            if (segmentoValido(seg)) {
                atual.insert(fim, '.');
                construir(atual, fim + 1, pontos + 1);
                atual.deleteCharAt(fim);
            }
        }
    }

    private boolean segmentoValido(String s) {
        if (s.charAt(0) == '0' && s.length() > 1) return false;
        int valor = 0;
        for (char c : s.toCharArray()) {
            valor = valor * 10 + (c - '0');
            if (valor > 255) return false;
        }
        return true;
    }
}

78. Subconjuntos

Dado um array de inteiros distintos, retornar todos os subconjuntos (incluindo vazio e o próprio aray).

Abordagem: backtracking que acumula o subconjunto atual antes de explorar ramificações. A cada nível, adiciona-se um elemento a partir do índice atual.

class SolucaoSubsets {
    List<List<Integer>> resultado = new ArrayList<>();
    List<Integer> atual = new ArrayList<>();

    public List<List<Integer>> subconjuntos(int[] nums) {
        gerar(nums, 0);
        return resultado;
    }

    private void gerar(int[] nums, int inicio) {
        resultado.add(new ArrayList<>(atual));
        for (int i = inicio; i < nums.length; i++) {
            atual.add(nums[i]);
            gerar(nums, i + 1);
            atual.remove(atual.size() - 1);
        }
    }
}

90. Subconjuntos com Duplicatas

Similar ao anterior, mas o array pode conter elementos repetidos. A solução deve evitar subconjuntos duplicaods.

Estratégia: ordenar o array e, no mesmo nível de recursão, ignorar elementos iguais ao enterior (poda de árvore horizontal).

class SolucaoSubsetsComDuplicatas {
    List<List<Integer>> resultado = new ArrayList<>();
    List<Integer> atual = new ArrayList<>();

    public List<List<Integer>> subconjuntosComDuplicatas(int[] nums) {
        Arrays.sort(nums);
        gerar(nums, 0);
        return resultado;
    }

    private void gerar(int[] nums, int inicio) {
        resultado.add(new ArrayList<>(atual));
        for (int i = inicio; i < nums.length; i++) {
            if (i > inicio && nums[i] == nums[i - 1]) continue;
            atual.add(nums[i]);
            gerar(nums, i + 1);
            atual.remove(atual.size() - 1);
        }
    }
}