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 is clearly run in exponential time.

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

Thank You.