There are n people, and an integer array p with size m. Each p[i] records the number of people that can be covered by the umbrella of type i. Each type can be picked multiple times. What is the minimal number of umbrellas to cover exactly n people?

ex. n = 4, m = 2, p[0] = 2, p[1] = 4. The answer is 1.

ex. n = 1, m = 1, p[0] = 2. The answer is -1.

  • This is a backtracking problem.
  • whenever the recursion is returned back, the selected element of the current iteration has to be removed out, so that the next iteration can continue.
#include <iostream>
#include <vector>
using namespace std;

int combSum(int sum, vector<int>& types);
void backTracking(vector<int>& types, int& mini, int& count, int& residual, int head, bool& solution);

int main()
{
   int sum;
   cout << "Enter a number as sum" << endl;
   cin >> sum;

   int len;
   cout << "Enter the size of integer array" << endl;
   cin >> len;

   vector<int> types(len);
   cout << "Enter the numbers of the array" << endl;
   for(int i = 0; i < types.size(); ++i) cin >> types[i];

   cout << "The minimum of numbers is " << combSum(sum, types) << " ";

   return 0;
}

int combSum(int sum, vector<int>& types)
{
    int residual = sum;
    int mini = sum;
    int count = 0;
    bool solution = false;
    backTracking(types, mini, count, residual, 0, solution);
    if(solution) return mini;
    return -1;
}

void backTracking(vector<int>& types, int& mini, int& count, int& residual, int head, bool& solution)
{
    for(int i = head; i < types.size(); ++i)
    {
        residual -= types[i];
        count++;
        if(residual == 0)
        {
            mini = (mini > count) ? count : mini;
            solution = true;
        }
        else if(residual > 0)
        {
            backTracking(types, mini, count, residual, i, solution);
        }
        count--;
        residual += types[i];
    }
}
comments powered by Disqus