LeetCode DayBackTracking Partie 2

39. Somme combinée

Étant donné un tableau de candidats entiers distincts et une cible entière cible, renvoie une liste de toutes les combinaisons uniques de candidats où la somme des nombres choisis correspond à la cible. Vous pouvez retourner les combinaisons dans n'importe quel ordre.

Le même nombre peut être choisi parmi les candidats un nombre illimité de fois. Deux combinaisons sont uniques si le
fréquence
d'au moins un des numéros choisis est différent.

Les cas de test sont générés de telle sorte que le nombre de combinaisons uniques qui totalisent la cible soit inférieur à 150 combinaisons pour l'entrée donnée.

Exemple 1 :

Entrée : candidats = [2,3,6,7], cible = 7
Sortie : [[2,2,3],[7]]
Explication :
2 et 3 sont candidats, et 2 + 2 + 3 = 7. Notez que 2 peut être utilisé plusieurs fois.
7 est candidat, et 7 = 7.
Ce sont les deux seules combinaisons.
Exemple 2 :

Entrée : candidats = [2,3,5], cible = 8
Sortie : [[2,2,2,2],[2,3,3],[3,5]]
Exemple 3 :

Entrée : candidats = [2], cible = 1
Sortie : []

Contraintes :

1 <= candidats.length <= 30
2 <= candidats[i] <= 40
Tous les éléments des candidats sont distincts.
1 <= cible <= 40

Page originale

La différence entre cette question et les questions résolues hier n'est pas très grande.


Le BackTracking fonctionne toujours bien pour rechercher la possibilité de profondeur et utiliser une boucle pour le contrôle de la largeur.


La partie qui nécessite une attention particulière est qu'ici nous pouvons ajouter les mêmes éléments et ensuite garder l'ensemble de la combinaison unique.

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> combs = new LinkedList<>();
        backTracking(list, combs, candidates, target, 0, 0);
        return list;
    }

    public void backTracking(List<List<Integer>>list, List<Integer> combs, int[] candidates, int target, int sum, int start){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=start; i<candidates.length; i++){
            combs.add(candidates[i]);
            sum += candidates[i];
            backTracking(list, combs, candidates, target, sum, i);
            combs.remove(combs.size()-1);
            sum -= candidates[i];
        }




</p>
<h2>
  
  
  40. Somme combinée II
</h2>

<h3>
  
  
  Délai dépassé
</h3>



<pre class="brush:php;toolbar:false">    Set<List<Integer>> set = new HashSet<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0);

        return new ArrayList<>(set);
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum){
        if(sum > target){
            return;
        }
        if(sum == target){
            set.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum);
            sum -= candidates[i];
            combs.remove(combs.size()-1);

        }
    }

Parce que certains éléments ont été utilisés précédemment, par ex. [1,1,1,2,3] 112 a été utilisé dans la première récursion mais la boucle traversera tous les éléments qui commencent de 1 à 3 et il y a trois « 1 », donc quand il s'agit du deuxième « 1 », la combinaison 112 sera également trouvée, qui a été trouvée dans les étapes de récursivité précédentes, nous devrions donc réduire ces étapes redondantes (de la même manière, cela peut se produire dans la traversée de la récursivité et dans la transversale de la récursivité également.

Résoudre le problème

    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<Integer> combs = new LinkedList<>();
        Arrays.sort(candidates);
        backTracking(combs, target, candidates, 0, 0, false);

        return list;
    }

    public void backTracking(List<Integer> combs, int target, int[]candidates, int start, int sum, boolean horizon){
        if(sum > target){
            return;
        }
        if(sum == target){
            list.add(new ArrayList<>(combs));
        }

        for(int i=start; i<candidates.length; i++){
            if(candidates[i] + sum > target){
                continue;
            }

            if(i!=0 && candidates[i] == candidates[i-1] && horizon){
                continue;
            }

            sum += candidates[i];
            combs.add(candidates[i]);
            backTracking(combs, target, candidates, i+1, sum, false);
            sum -= candidates[i];
            combs.remove(combs.size()-1);
            horizon = true;
        }
    }

131. Partitionnement palindrome

Étant donné une chaîne s, partitionnez s telle que chaque
sous-chaîne
de la partition est un
palindrome
. Renvoie tous les partitionnements palindromes possibles de s.

Exemple 1 :

Entrée : s = "aab"
Sortie : [["a","a","b"],["aa","b"]]
Exemple 2 :

Entrée : s = "a"
Sortie : [["a"]]

Contraintes :

1 <= s.length <= 16
s ne contient que des lettres anglaises minuscules.
Page originale

    List> list = new ArrayList<>();
    public List> partition(String s) {
        List combs = new ArrayList<>();

        backTracking(combs, new StringBuilder(s), 0);
        return list;
    }

    public void backTracking(List combs, StringBuilder str, int start){
        if(start == str.length()){
            list.add(new ArrayList<>(combs));
            return;
        }

        for(int i=1; i+start <= str.length(); i++){

            String cur = str.substring(start, start+i);

            if(!isParlindrome(cur)){
                continue; 
            } 

            combs.add(cur);
            backTracking(combs, str, start+i);
            combs.remove(combs.size()-1);
        }

    }

    public boolean isParlindrome(String s){
        int left = 0;
        int right = s.length()-1;

        while(left
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!