Restauration d'adresses IP valides

La reconstruction d'adresses IP à partir d'une chaîne numérique nécessite une approche de partitionnement avec validation. Une adresse IP valide doit contenir exactement quatre segments, chaque segment étant un entier entre 0 et 255 sans zéro non significatif.

Exemples d'adresses valides : "192.168.1.1", "10.0.0.1"
Exemples d'adresses invalides : "192.168.001.1", "256.0.0.1"

Implémentation par backtracking

class SolutionIP:
    def reconstruire_adresses_ip(self, chaine: str) -> List[str]:
        resultats = []
        segments = []
        
        def est_valide(segment: str) -> bool:
            if not segment:
                return False
            if segment[0] == '0' and len(segment) > 1:
                return False
            valeur = int(segment)
            return 0 <= valeur <= 255
        
        def explorer(debut: int):
            if len(segments) == 3:
                segment_final = chaine[debut:]
                if est_valide(segment_final):
                    adresse = ".".join(segments) + "." + segment_final
                    resultats.append(adresse)
                return
            
            for fin in range(debut, min(debut + 3, len(chaine))):
                segment_courant = chaine[debut:fin+1]
                if est_valide(segment_courant):
                    segments.append(segment_courant)
                    explorer(fin + 1)
                    segments.pop()
        
        explorer(0)
        return resultats

Génération de tous les sous-ensembles

Le problème de génération de sous-ensembles consiste à produire toutes les combinaisons possibles d'éléments d'un tableau, y compris l'ensemble vide et l'ensemble complet.

Approche exhaustive

class SolutionSousEnsembles:
    def generer_sous_ensembles(self, elements: List[int]) -> List[List[int]]:
        sous_ensembles = []
        courant = []
        
        def generer(depart: int):
            sous_ensembles.append(courant.copy())
            if len(courant) == len(elements):
                return
            
            for i in range(depart, len(elements)):
                courant.append(elements[i])
                generer(i + 1)
                courant.pop()
        
        generer(0)
        return sous_ensembles

Sous-ensembles avec éléments dupliqués

Lorsque le tableau contient des doublons, il est nécessaire d'éviter la génération de sous-ensembles identiques.

Solution avec élimination des doublons

class SolutionSousEnsemblesDupliques:
    def sous_ensembles_sans_doublons(self, elements: List[int]) -> List[List[int]]:
        sous_ensembles = []
        selection = []
        elements.sort()
        
        def explorer(index_depart: int):
            sous_ensembles.append(selection.copy())
            
            for i in range(index_depart, len(elements)):
                if i > index_depart and elements[i] == elements[i-1]:
                    continue
                selection.append(elements[i])
                explorer(i + 1)
                selection.pop()
        
        explorer(0)
        return sous_ensembles