Baumdiagramm rekursiv durchlaufen

Hallo,
ich stehen momentan ziemlich auf dem Schlauch. Ich habe eine vector mit Münzen. Diesen soll ich nun darauf testen, ob es möglich ist einen bestimmten Geldwert daraus zu bilden. Rekursiv sollte sich das relativ einfach lösen lassen, ich komme gerade nur nicht drauf, wie ich das am besten angehen soll. Ich habe mir bis jetzt dieses Baumdiagramm überlegt(es sind nicht alle Äste vollständig gezeichnet):
http://www.youscreen.de/yvmphivsq47.jpg

Wenn man von einer vector Größe von 5 ausgeht, dann hat man die Wahl zwischen 5 Einträgen, wählt man einen, so hat man nur noch 4 zur Auswahl, wählt man einen weiteren nur noch 3, einen weiteren nur noch 2 und schließlich einen letzen.

Soweit sollte alles stimmen, nur habe ich keine Idee, wie man so etwas rekursiv umsetzt.

Mein Ansatz der Methode:

void process(std::vector<int> &münzen, int curr_pos, std::vector<int> münzen_used) //münzen_used: hier wird gespeichert, welche Münzen ausgewählt worden sind
{
    if (curr_pos < 0 || curr_pos >= münzen.size()) // out of range
		return;

    //hier habe ich Probleme

}

Hausaufgabe?

Ich würde die Signatur anders wählen:

void process(const std::vector<int> &muenzen, int target_value,
             vector<int> &gewaehlt, size_t curr_pos = 0, int current_sum = 0)

Also insbesondere muss ich doch wissen, welches Ziel ich habe und die Summe der aktuell ausgewählten Münzen kann auch nicht schaden.

Tipp: in process muss du 2x process selbst aufrufen, jeweils mit curr_pos+1, einmal mit und einmal ohne hinzugefügter Münze.

Und jetzt: selber probieren!

Belli

Ich habe hier mal zwei Varianten aus meinen alten Codeschnipseln:

bool erreichbar(int b)
{
	if(b == 0)
		return true;
	if(b < 0)
		return false;

	for(int i = 0; i < m.size(); ++i)
	{
		if(erreichbar(b - m[i]))
		{
			r.push_back(m[i]);
			return true;
		}
	}

	return false;
}

bool erreichbar1(int b, int start = 0)
{
	if(b == 0)
		return true;
	if(b < 0)
		return false;

	for(int i = start; i < m.size(); ++i)
	{
		if(erreichbar1(b - m[i], start + 1))
		{
			r.push_back(m[i]);
			return true;
		}
	}

	return false;
}

m ist ein - global definierter - Vektor, der die zur Verfügung stehenden Münzen enthält. r ist ein global definierter leerer Vektor, der mit den Münzen befüllt wird, die die gesuchte Summe ergeben.
Beide Varianten werden mit der gesuchten Summe als Parameter aufgerufen.
Die erste Variante verwendet die zur Verfügung stehenden Münzen mehrfach, in m sind also lediglich die verschiedenen Münzgrößen erforderlich.
Die zweite Variante verwendet jede Münze nur einmal.
Seien die Münzen in m zB: 5, 2 und 1, dann findet Variante 1 die Summen 10, 15, 22 usw. Variante 2 findet die Summen 5, 7, 8, 3 ...
Für Variante 2 macht es also Sinn, m zB: mit 5, 5, 5, 2, 2, 1 zu füllen, für den Aufruf von Variante 1 nicht.

Super danke, das war genau, wonach ich gesucht habe