Kombinacje rekurencyjnie

Witam!

Mam problem z pewnym zadaniem, które musi być wykonane rekurencyjnie. Co to jest rekurencja i jak jej używać dokładnie wiem ale w tym przypadku wszystkie moje wysiłki zawiodły, dlatego też proszę Was o pomoc i wskazanie błędu w poniższym kodzie. Pełna treść zadania:

Dla danego łańcucha znaków input długości n, chcemy wypisać każdy kombinację w łańcuch u
danej długości k <= n na wyjście konsoli. Na przykład, jeżeli input jest równy abcd i k = 3, to program
wypisze do konsoli (kolejność wierszy jest nieważna):
abc
abd
acd
bcd
Piszemy taki program lancuchy, gdzie input i k są czytane wtedy, gdy program jest
uruchamiany. To znaczy, że użytkownik może np. napisać w konsoli:
> ./lancuchy abcd 3

Zadanie. Proszę zdefiniować rekurencyjną funkcję print poniżej, gdzie **mamy** zawiera
pierwsze litery naszego łańcuchu znaków, **potem** zawiera część danego łańcuchu, której
jeszcze można użyć, i **i** liczy, ile znaki jeszcze można dodać do mamy.

#include <iostream>
#include <string>
#include <stdlib.h> /* atoi */
using namespace std;
void print(string mamy, string potem, unsigned int i) {
// tutaj dodać linijki, używając rekurencji
}
int main(int argc, char **argv)
{
if ( argc<3 )
return 1; // za mało argumentów
std::string input = argv[1];
unsigned int k = atoi (argv[2]); // ASCII to int
if ( k > input.length() )
return 1; // k za duży
print ("", input, k );
} 

Moja próba poradzenia sobie z problemem:

 #include "stdafx.h"

#include <iostream>
#include <string>

void print(std::string mamy, std::string potem, unsigned int i);

int main(int argc, char **argv)
{
	if (argc < 3)
	{
		return 1;
	}

	std::string input = argv[1];
	unsigned int k = atoi(argv[2]);

	if (k > input.length())
	{
		return 1;
	}

	print("", input, k);
	return 0;
}

void print(std::string mamy, std::string potem, unsigned int i)
{

	std::string left_branch(potem.begin(), potem.end());
	std::string right_branch(potem.begin() + 1, potem.end());

	std::string temp;
		
	if (i != 0)
	{ 
		potem = left_branch;
		mamy += potem[0];
		potem.erase(0, 1);
		print(mamy, potem, i - 1); 
	}
	else
	{
		std::cout << mamy << std::endl;
		
		return;
	}
		
	if (i != 0) 
	{ 
		potem = right_branch;
		mamy += potem[0];
		potem.erase(0, 1);
		print(mamy, potem, i - 1); 
	}
	else
	{
		std::cout << mamy << std::endl;
		return;
	}

}

Rekurencyjne liczenie kombinacji:
http://4programmers.net/Forum/Newbie/256661-wszystkie_kombinacje_6_liczb_z_9-elementowego_zbioru?p=1167378#id1167378

Problem polega właśnie na tym, że jestem ograniczony prototypem funkcji.

Kolejna próba. Tym razem działa dla podanego w zadaniu przykładu, ale dla innych nie zwraca już poprawnych wartości.

void print(std::string mamy, std::string potem, unsigned int i)
{	
	std::string left_branch;
	std::string right_branch;
	
	if (i != 0)
	{

		left_branch.assign(potem.begin(), potem.end());
		if (left_branch.size() >= 2)
		{
			right_branch.assign(potem.begin() + 1, potem.end());
		}
		
		if (left_branch.size() > 0) { mamy += left_branch[0]; } else { return; }
		left_branch.erase(0, 1);
		print(mamy, left_branch, i - 1);
		mamy.pop_back();


		if (right_branch.size() > 0) { mamy += right_branch[0]; } else { return; }
		right_branch.erase(0, 1);
		print(mamy, right_branch, i - 1);
		mamy.pop_back();
	}
	else
	{
		std::cout << mamy << std::endl;
		return;
	}
}
 

mój znajomy z googla zadaje takie pytanie na rozmowie kwalifikacyjnej, tylko lekko w innej formie, takie mi zadanie kiedyś zadał to je rozwiązałem;

mapa to odzwierciedlenie liter na klawiszach telefonu komórkowego;

#include <iostream>
#include <map>
#include <vector>
#include <thread>
#include <chrono>
 
typedef std::map<char, std::vector<char> > binds_tt;
binds_tt binds { { '2', { 'A', 'B', 'C' } },
				 { '3', { 'D', 'E', 'F' } },
				 { '4', { 'G', 'H', 'I' } },
				 { '5', { 'J', 'K', 'L' } },
				 { '6', { 'M', 'N', 'O' } },
				 { '7', { 'P', 'Q', 'R', 'S' } },
				 { '8', { 'T', 'U', 'V' } },
				 { '9', { 'W', 'X', 'Y', 'Z' } } };
 
void calculate(std::string phoneNumber, std::string result, std::vector<std::string>& results)
{
	if(!phoneNumber.size()) {
		results.push_back(result);
		return;
	}
 
	auto const& boundLetters = binds[*std::begin(phoneNumber)];
	for(auto const& letter : boundLetters) {
		result += letter;
		calculate(phoneNumber.substr(1), result, results);
 
		result = result.substr(0, result.size() - 1);
	}
}
 
int main()
{
	std::string number("2349");
	std::vector<std::string> results;
	calculate(number, std::string(""), results);
 
	for(auto const& s : results)
		std::cout << s << std::endl;
}

http://melpon.org/wandbox/permlink/LMfuX6QWsXty5up3