Leetcode 47. Full arrangement II

Jusqu'à présent, j'ai écrit 600Problème d'algorithme multicanal,Certains d'entre eux ont été triéspdfDocumentation,Pour l'instantEn tout.1000Plusieurs pages（Et ça va augmenter）,Téléchargement gratuit
Télécharger le lien：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
Code d'extraction：6666

C'est la même chose qu'avant.593,Le problème classique de l'algorithme de rétrosuivi-Disposition complètePresque., Mais il y a Dupliquer les chiffres ,Mais...593 La question n'est pas répétée . S'il y a des chiffres en double, il y aura certainement des combinaisons en double , Donc cette question doit filtrer les combinaisons répétées . Que se passe - t - il si vous ne Filtrez pas , Prenons l'exemple de l'exemple 1 et regardons le graphique （ Pour distinguer le premier 1Et le deuxième1, J'ai utilisé des marques noires et rouges ）.

Comment filtrer les nombres dupliqués , Une façon est de trouver tous les résultats combinés , Puis filtrer les combinaisons répétées dans ce résultat . C'est mieux si la combinaison est une chaîne , Mais voici un tableau , Tous les tableaux en deux sont trop complexes , De cette façon, nous n'envisageons pas .

En plus de l'une des solutions décrites ci - dessus, il y a une autre façon dont nous disons souvent Couper, Comment couper ？ Parce que pour filtrer les duplicatas , Seuls les chiffres dupliqués donnent des résultats dupliqués . Donc la première étape est de faire le tableau Trier, Le même nombre après le tri doit être à côté .

Les codes sont les suivants:

public List<List<Integer>> permuteUnique(int[] nums) {
    
    //Trier d'abord le tableau, Ce faisant, les mêmes valeurs doivent être contiguës dans le tableau ,
    // Filtrer facilement les résultats en double 
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //booleanTableau,used[i]Élément de représentationnums[i] A - t - on déjà visité 
    boolean[] used = new boolean[nums.length];
    // Effectuer un algorithme de rétrosuivi 
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    
    // Si tous les éléments du tableau sont utilisés , C'est comme arriver au noeud foliaire ,
    // Nous ajoutons directement les éléments du chemin du noeud racine au noeud foliaire courant 
    //Au rassemblementresMoyenne
    if (tempList.size() == nums.length) {
    
        res.add(new ArrayList<>(tempList));
        return;
    }
    // Traverser les éléments du tableau 
    for (int i = 0; i < nums.length; i++) {
    
        // Si elle a déjà été utilisée ,Sauter directement
        if (used[i])
            continue;
        //Attention!, Ici, il faut couper les combinaisons répétées 
        // Si l'élément courant est le même que l'élément précédent , Et le précédent n'a pas été utilisé , On saute aussi 
        if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
            continue;
        // Sinon, nous utiliserons l'élément courant , Marque - le comme utilisé 
        used[i] = true;
        // Mettez l'élément courant nums[i]Ajouter àtempListMoyenne
        tempList.add(nums[i]);
        //Récursion,Similaire ànTraversée de l'arbre de fourche,Continuez à descendre.
        backtrack(nums, used, tempList, res);
        // Quand la récursion est terminée, elle revient en arrière , Pour revenir en arrière et annuler le choix 
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}

En plus de la coupe dont il est question ci - dessus , Y a - t - il d'autres façons de couper ,En fait, il y a.C'est Quand vous traversez le nombre actuel , Si le nombre actuel est le même que le nombre précédent dans le tableau , Et le chiffre précédent a été utilisé , On va sauter la branche actuelle , C'est - à - dire couper la branche actuelle （ Contrairement à ce qui précède ）.Comme le montre la figure ci - dessous

C'est ce dont nous parlions 590,L'algorithme de rétrosuivi résout le nombre de tableaux carrés Dernière mention dans , Les deux méthodes de coupe sont acceptables , L'un est de couper toute la branche , L'un d'eux est de couper des brindilles sous chaque brindille . Il est évident que la première coupe est plus efficace ,Voyons le Code.

public List<List<Integer>> permuteUnique(int[] nums) {
    
    //Trier d'abord le tableau, Ce faisant, les mêmes valeurs doivent être contiguës dans le tableau ,
    // Filtrer facilement les résultats en double 
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //booleanTableau,used[i]Élément de représentationnums[i] A - t - on déjà visité 
    boolean[] used = new boolean[nums.length];
    // Effectuer un algorithme de rétrosuivi 
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    
    // Si tous les éléments du tableau sont utilisés , C'est comme arriver au noeud foliaire ,
    // Nous ajoutons directement les éléments du chemin du noeud racine au noeud foliaire courant 
    //Au rassemblementresMoyenne
    if (tempList.size() == nums.length) {
    
        res.add(new ArrayList<>(tempList));
        return;
    }
    // Traverser les éléments du tableau 
    for (int i = 0; i < nums.length; i++) {
    
        // Si elle a déjà été utilisée ,Sauter directement
        if (used[i])
            continue;
        //Attention!, Ici, il faut couper les combinaisons répétées 
        // Si l'élément courant est le même que l'élément précédent , Et le précédent a été utilisé , On saute aussi 
        if (i > 0 && nums[i - 1] == nums[i] && used[i - 1])
            continue;
        // Sinon, nous utiliserons l'élément courant , Marque - le comme utilisé 
        used[i] = true;
        // Mettez l'élément courant nums[i]Ajouter àtempListMoyenne
        tempList.add(nums[i]);
        //Récursion,Similaire ànTraversée de l'arbre de fourche,Continuez à descendre.
        backtrack(nums, used, tempList, res);
        // Quand la récursion est terminée, elle revient en arrière , Pour revenir en arrière et annuler le choix 
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}

Les deux codes ci - dessus sont très similaires , La seule différence, c'est la ligne suivante ,Les autres sont les mêmes.

 if (i > 0 && nums[i - 1] == nums[i] && used[i - 1])

Si on choisit , Nous choisirons certainement la première voie , Couper toute la grande branche .