Énoncé: On vous donne un tableau d'entiers distincts candidats et un entier cible cible. Trouvez toutes les combinaisons uniques dans candidats où la somme des nombres égale cible. Le même nombre peut être choisi un nombre illimité de fois dans candidats. Deux combinaisons sont considérées comme différentes si au moins un nombre a une fréquence différente.

Solution:

class SolutionSomme {
private:
    vector<vector>> resultats;
    vector<int> combinaisonActuelle;
    
    void explorer(vector<int>& candidats, int cible, int sommeActuelle, int position) {
        if (sommeActuelle > cible) {
            return;
        }
        if (sommeActuelle == cible) {
            resultats.push_back(combinaisonActuelle);
            return;
        }
        for (int i = position; i < candidats.size(); ++i) {
            sommeActuelle += candidats[i];
            combinaisonActuelle.push_back(candidats[i]);
            explorer(candidats, cible, sommeActuelle, i);
            sommeActuelle -= candidats[i];
            combinaisonActuelle.pop_back();
        }
    }
    
public:
    vector<vector>> trouverCombinaisons(vector<int>& candidats, int cible) {
        resultats.clear();
        combinaisonActuelle.clear();
        explorer(candidats, cible, 0, 0);
        return resultats;
    }
};</int></vector></int></int></vector>

Problème 2: Somme de combinaisons II

Énoncé: Étant donné une collection de nombres candidats candidats et un nombre cible cible, trouvez toutes les combinaisons uniques dans candidats où la somme des candidast égale cible. Chaque nombre dans candidats ne peut être utilisé qu'une seule fois dans la combinaison. Remarque: L'ensemble des solutions ne doit pas contenir de combinaisons en double.

Solution:

class SolutionSommeII {
private:
    vector<vector>> resultats;
    vector<int> combinaisonActuelle;
    
    void explorer(vector<int>& candidats, int cible, int sommeActuelle, int position) {
        if (sommeActuelle > cible) {
            return;
        }
        if (sommeActuelle == cible) {
            resultats.push_back(combinaisonActuelle);
        }
        for (int i = position; i < candidats.size() && sommeActuelle + candidats[i] <= cible; ++i) {
            if (i > position && candidats[i] == candidats[i-1]) {
                continue;
            }
            sommeActuelle += candidats[i];
            combinaisonActuelle.push_back(candidats[i]);
            explorer(candidats, cible, sommeActuelle, i+1);
            sommeActuelle -= candidats[i];
            combinaisonActuelle.pop_back();
        }
    }
    
public:
    vector<vector>> trouverCombinaisonsUniques(vector<int>& candidats, int cible) {
        resultats.clear();
        combinaisonActuelle.clear();
        vector<bool> marque(candidats.size(), false);
        sort(candidats.begin(), candidats.end());
        explorer(candidats, cible, 0, 0);
        return resultats;
    }
};</bool></int></vector></int></int></vector>

Problème 3: Partition de palindromes

Énoncé: On vous donne une chaîne de caractères s, partitionnez s de telle sorte que chaque sous-chaîne de la partition soit un palindrome. Renvoyez toutes les partitions possibles de palindromes de s. Un palindrome est une chaîne qui se lit de la même manière de l'avant et de l'arrière.

Solution:

class SolutionPalindrome {
private:
    vector<vector>> resultats;
    vector<string> partitionActuelle;
    
    void explorer(const string& s, int positionDepart) {
        if (positionDepart >= s.size()) {
            resultats.push_back(partitionActuelle);
            return;
        }
        for (int i = positionDepart; i < s.size(); ++i) {
            if (estPalindrome(s, positionDepart, i)) {
                string sousChaine = s.substr(positionDepart, i - positionDepart + 1);
                partitionActuelle.push_back(sousChaine);
            } else {
                continue;
            }
            explorer(s, i + 1);
            partitionActuelle.pop_back();
        }
    }
    
    bool estPalindrome(const string& s, int debut, int fin) {
        for (int i = debut, j = fin; i < j; ++i, --j) {
            if (s[i] != s[j]) {
                return false;
            }
        }
        return true;
    }
    
public:
    vector<vector>> partitionner(string s) {
        resultats.clear();
        partitionActuelle.clear();
        explorer(s, 0);
        return resultats;
    }
};</vector></string></vector>