@dmitriyivvvv

Как найти все комбинации, из которых можно составить n?

Добрый вечер! В общем имеется некое множество [100, 50, 25, 10, 5, 1] и n. Мне нужно найти все комбинации, из которых можно составить n. Например для n = 100 и множества выше ответом будет 194 комбинации. Так как с алгоритмами у меня беда, не знаю даже как правильно сформулировать чтобы загуглить.
  • Вопрос задан
  • 307 просмотров
Решения вопроса 1
#include <iostream>
#include <vector>

std::vector<int> arr = { 100, 50, 25, 10, 5, 1 };
int n = 100;
int matches = 0;

void calc( int val, unsigned int offs ) {
  if( val == n ) {
    matches++;
    return;
  } else if( val > n ) {
    return;
  }
  for( unsigned int i = offs; i < arr.size(); ++i ) {
    calc( val + arr[i], i );
  }
}

int main( int argc, char** argv ) {
  calc( 0, 0 );
  std::cout << matches << std::endl;
  return( EXIT_SUCCESS );
}
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 1
Может быть что-то вроде этого: https://prog-cpp.ru/combinations/?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы