Hello everyone,

I have successfully managed to write a recursive program to print all possible combinations of getting a coin change, let's say value:

void print_possible_change(vector<int> &change, int beginWith, int value, vector<vector<int>> &res, vector<int> &temp){
	if(value == 0){
		res.push_back(temp);
	}

	for(int i = beginWith; i < change.size() && change[i] <= value; ++i){
		temp.push_back(change[i]);
		print_possible_change(change, i, value - change[i], res, temp);
		temp.pop_back();
	}
}

The final result of all combinations is stored in res.

This approach clearly runs in exponential time.

Is there an approach that runs in quadratic time or less?

Thank You.