algorithm - Number Formation -

given 3 integers x,y , z need find sum of numbers formed having 4 atmost x times , having 5 atmost y times , having 6 atmost z times digit.

note: numbers can contain 4,5,6 digits.

eg: 1 1 1

output: 3675

explanation: ans input 4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675

i tried coming dp approach similar in finding ugly numbers. no hope?

how solve problem?

i think super hard problem. it?

there simple two-part solution problem.

you need:

1. an algorithm finding distinct orderings of array.
2. an algorithm creates arrays in digits of interest included varying numbers of times.

for (1) can use std::next_permutation() along unordered_set.

for (2) build recursive function constructs array.

the following program accomplishes this:

#include <iostream> #include <algorithm> #include <vector> #include <numeric>  //convert array of digits integer int vectonumber(const std::vector<int> &to_permute){   int num   = 0;   int tens  = 1;   for(int = to_permute.size()-1;i>=0;i--,tens*=10)     num+=to_permute[i]*tens;   return num; }  void permuter(std::vector<int> to_permute, std::vector<int> &numbers_to_add){   //sorting necessary step before can use `std::next_permutation`   std::sort(to_permute.begin(),to_permute.end());   //loop through every permutation of `to_permute`   {     numbers_to_add.push_back(vectonumber(to_permute));   } while(std::next_permutation(to_permute.begin(), to_permute.end())); }  //build array permute void builder(   const std::vector<int> &values,   //digits use   const std::vector<int> &counts,   //maximum times use each digit   std::vector<int> &to_permute,     //current array   std::vector<int> &numbers_to_add, //numbers adding   int pos                           //digit considering ){   //since to_permute used @ each level of recursion, must preserve   //at each level can reverse effects of deeper levels of   //recursion when moving shallower levels.   const auto original_tp = to_permute;    if(pos<values.size()){     //add more , more copies of digit `to_permute` array,     //the value specified `counts[pos]`     for(int i=0;i<counts[pos];i++){       builder(values,counts,to_permute,numbers_to_add,pos+1);       to_permute.push_back(values[pos]);     }     builder(values,counts,to_permute,numbers_to_add,pos+1);   } else {     //we've run out of digits consider, generate of     //permutations of digits     permuter(to_permute,numbers_to_add);   }   to_permute = original_tp; }  int main(){   std::vector<int> values = {{4,5,6}}; //digits use   std::vector<int> counts = {{1,1,1}}; //maximum number of times use each digit    std::vector<int> to_permute;     //holds numbers permuting   std::vector<int> numbers_to_add; //holds numbers wish add    //collect numbers want add   builder(values,counts,to_permute,numbers_to_add,0);    for(auto x: numbers_to_add)     std::cout<<x<<std::endl;    std::cout<<"sum = "<<std::accumulate(numbers_to_add.begin(),numbers_to_add.end(),0)<<std::endl; } 

output:

0 4 5 6 45 46 54 56 64 65 456 465 546 564 645 654 sum = 3675