Cet algorithme fonctionne-t-il réellement? Somme des sous-ensembles algorithme de retour en arrière

Le code implémente l'algorithme correctement, sauf que vous n'avez pas appliqué la logique de matrice unique basée sur votre boucle de sortie. Modification: xxx pré>

à: p> xxx pré>

Selon la manière dont vous avez organisé votre code, assurez-vous que prometteur code> est défini quand sos code> est défini. p>

Voir il exécutoire sur .Il . Sortie: P>

0 1 0 0 0 1
0 0 1 1 1 0

Alors oui, comme les autres l'ont souligné, vous avez trébuché sur l'indice de tableau 1 basé.

Cela de côté, je pense que vous devriez demander à l'auteur d'un retour partiel de l'argent que vous avez payé pour le livre, car la logique de Son code est trop compliqué. P>

Un bon moyen de ne pas courir dans les problèmes de limites est de ne pas utiliser C ++ (attendre la grêle de bowvotes pour cette lol). P>

Il n'y a que 3 cas à Test pour: p>

• La valeur du candidat est supérieure à ce qui reste. (éclaté) li>
• La valeur candidate est exactement ce qui reste. li>
• la valeur candidate est inférieure à ce qui reste. li> ul>

  Le la fonction prometteuse code> tente d'exprimer cela, puis le résultat de cette fonction est à nouveau testé dans la fonction principale sos code>. p>.

  Mais cela pourrait sembler aussi simple que ceci: p> xxx pré>

  Maintenant, il n'est pas impossible d'obtenir un filet de sécurité similaire lors de l'écriture du code C ++. Mais cela prend la détermination et une décision consciente sur ce que vous êtes prêt à faire face et à quoi ne pas. Et vous devez être prêt à taper quelques lignes supplémentaires pour accomplir ce que les 10 lignes de haskell font. P>

  Tout d'abord, j'ai été dérangé par toute la complexité de l'indexation et de la plage de la plage dans le code C ++ d'origine. Si nous regardons notre code Haskell (qui fonctionne avec des listes), Il est confirmé que nous n'avons pas besoin d'un accès aléatoire du tout. Nous ne considérons jamais seulement le début des articles restants. Et nous appouvons une valeur au chemin (dans HASKELL, nous appendons à l'avant parce que la vitesse) et, éventuellement, nous appendons une combinaison trouvée à l'ensemble de résultats. Avec cela à l'esprit, la peine avec les indices est un peu sur le dessus. P>

  Deuxièmement, je préfère la façon dont la fonction de recherche semble - montrant les 3 tests cruciaux sans aucun bruit qui leur entoure. Ma version C ++ devrait s'efforcer d'être aussi jolie. P>

  En outre, les variables globales sont ainsi de 1980 - nous n'aurons pas cela. Et renverser ces "globaux" dans une classe pour les cacher un peu est tellement 1995. Nous n'aurons pas cela non plus. P>

  et ici c'est! La mise en œuvre "plus sûre" C ++. Et plus jolie ... euh ... bien certains d'entre vous pourraient être en désaccord;) p>

  #include <cstdint>
  #include <vector>
  #include <iostream>
  
  using Items_t = std::vector<int32_t>;
  using Result_t = std::vector<Items_t>;
  
  // The C++ way of saying: deriving(Show)
  template <class T>
  std::ostream& operator <<(std::ostream& os, const std::vector<T>& value) 
  {
      bool first = true;
      os << "[";
      for( const auto item : value) 
      {
          if(first) 
          {
              os << item;
              first = false;
          }
          else
          {
              os << "," << item;
          }
      }
      os << "]";
      return os;
  }
  
  // So we can do easy switch statement instead of chain of ifs.
  enum class Comp : int8_t 
  {   LT = -1
  ,   EQ = 0
  ,   GT = 1
  };
  
  static inline 
  auto compI32( int32_t left, int32_t right ) -> Comp
  {
      if(left == right) return Comp::EQ;
      if(left < right) return Comp::LT;
      return Comp::GT;
  }
  
  // So we can avoid index insanity and out of bounds problems.
  template <class T>
  struct VecRange
  {
      using Iter_t = typename std::vector<T>::const_iterator;
      Iter_t current;
      Iter_t end;
      VecRange(const std::vector<T>& v)
          : current{v.cbegin()}
          , end{v.cend()}
      {}
      VecRange(Iter_t cur, Iter_t fin)
          : current{cur}
          , end{fin}
      {}
      static bool exhausted (const VecRange<T>&);
      static VecRange<T> next(const VecRange<T>&);
  };
  
  template <class T>
  bool VecRange<T>::exhausted(const VecRange<T>& range)
  {
      return range.current == range.end;
  }
  
  template <class T>
  VecRange<T> VecRange<T>::next(const VecRange<T>& range)
  {
      if(range.current != range.end)
          return VecRange<T>( range.current + 1, range.end );
      return range;   
  }
  
  using ItemsRange = VecRange<Items_t::value_type>;
  
  
  static void search( const ItemsRange items, int32_t target, Items_t path, Result_t& result)
  {
      if(ItemsRange::exhausted(items))
      {
          if(0 == target)
          {
              result.push_back(path);
          }
          return;
      }
  
      switch(compI32(*items.current,target))
      {
          case Comp::GT: 
              return;
          case Comp::EQ:
              {
                  path.push_back(*items.current);
                  result.push_back(path);
              }
              return;
          case Comp::LT:
              {
                  auto path1 = path; // hope this makes a real copy...
                  path1.push_back(*items.current);
                  search(ItemsRange::next(items), target - *items.current, path1, result);
                  search(ItemsRange::next(items), target, path, result);
              }
              return;
      }
  }
  
  int main(int argc, const char* argv[])
  {
      Items_t items{ 2, 10, 13, 17, 22, 42 };
      Result_t result;
      int32_t target = 52;
  
      std::cout << "Input: "  << items << std::endl;
      std::cout << "Target: " << target << std::endl;
      search(ItemsRange{items}, target, Items_t{}, result);
      std::cout << "Output: " << result << std::endl;
      return 0;
  }