Combinaison Somme

Question

Étant donné un ensemble de nombres de candidats (C) et un numéro de cible (T), trouver toutes les combinaisons uniques en C où le nombre de candidats sommes à T.

Le même nombre répété peut être choisi parmi C illimité nombre de fois.

All numbers (including target) will be positive integers. 
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak). 
The combinations themselves must be sorted in ascending order. 
CombinationA > CombinationB iff (a1 > b1) OR (a1 = b1 AND a2 > b2) OR … (a1 = b1 AND a2 = b2 AND … ai = bi AND ai+1 > bi+1) 
The solution set must not contain duplicate combinations. 

Exemple, candidat ensemble donné 2,3,6,7 et cibler 7, Un ensemble de la solution est:

[2, 2, 3] [7]

Le code de la solution est:

class Solution { 
    public: 

    void doWork(vector<int> &candidates, int index, vector<int> &current, int currentSum, int target, vector<vector<int> > &ans) { 
     if (currentSum > target) { 
      return; 
     } 
     if (currentSum == target) { 
      ans.push_back(current); 
      return; 
     } 
     for (int i = index; i < candidates.size(); i++) { 
      current.push_back(candidates[i]); 
      currentSum += candidates[i]; 

      doWork(candidates, i, current, currentSum, target, ans); 

      current.pop_back(); 
      currentSum -= candidates[i]; 
     } 

    } 

    vector<vector<int>> combinationSum(vector<int> &candidates, int target) { 
     vector<int> current; 
     vector<vector<int> > ans; 
     sort(candidates.begin(), candidates.end()); 
     vector<int> uniqueCandidates; 
     for (int i = 0; i < candidates.size(); i++) { 
      if (i == 0 || candidates[i] != candidates[i-1]) { 
       uniqueCandidates.push_back(candidates[i]); 
      } 
     } 
     doWork(uniqueCandidates, 0, current, 0, target, ans); 
     return ans; 
    } 
}; 

Maintenant, bien que je puisse comprendre la solution en prenant un exemple de cas, comment puis-je sortir avec une telle solution. Le travail principal va dans cette fonction:

for (int i = index; i < candidates.size(); i++) { 
     current.push_back(candidates[i]); 
     currentSum += candidates[i]; 

     doWork(candidates, i, current, currentSum, target, ans); 

     current.pop_back(); 
     currentSum -= candidates[i]; 
    } 

S'il vous plaît dites-moi comment comprendre le code ci-dessus et comment penser cette solution. Je peux résoudre les problèmes de récursion de base, mais ceux-ci semblent hors de portée. Merci pour votre temps.

Answer 1

donc ce que le code fait essentiellement est:

1. Trier l'ensemble donné de nombres en ordre croissant.
2. Supprimer les doublons de l'ensemble.
3. Pour chaque numéro de l'ensemble:
   • continuer à ajouter le même nombre, jusqu'à ce que la somme est soit supérieure ou égale à la cible.
   • Si elle est égale, enregistrez la combinaison.
   • S'il est plus grand, supprimez le dernier nombre ajouté (revenez à l'étape précédente) et commencez à ajouter le nombre suivant de l'ensemble à la somme.

Pour récursion compréhension, je voudrais commencer par des cas très simples. Voyons voir par exemple: Candidates: { 2, 2, 1 } Target: 4

Le tri et la suppression des doublons modifie l'ensemble {1, 2}.La séquence de récursivité sera:

• Somme = 1;
  • Somme = 1 + 1;
    • Somme = 1 + 1 + 1;
      • Somme = 1 + 1 + 1 + 1; (Identique à la cible, enregistrez la combinaison)
      • Somme = 1 + 1 + 1 + 2; (Plus grand que la cible, plus aucun numéro à ajouter)
    • Somme = 1 + 1 + 2; (Enregistrer la combinaison, plus aucun numéro à ajouter)
  • Somme = 1 + 2;
    • Somme = 1 + 2 + 2; (Plus grand, numéro plus)
• Somme = 2;
  • Somme = 2 + 2; (Save, ce dernier est la récursivité)