#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Can we build string 'word' using the letters we have?
bool word_buildable(string word, vector<int> letter_freq)
{
  for(int i=0;i<word.length();++i) {
    if(letter_freq[word[i]-'A']-- == 0)
	  return false;
  }
  return true;
}

void findAllPhrases(string partial_phrase, vector<int> letter_freq, vector<string> & output_phrases, vector<string> & dictionary) {
  for(int i=0;i<dictionary.size();++i) {
    if(word_buildable(dictionary[i], letter_freq)) {
	  string next_phrase = partial_phrase;
	  if(next_phrase != "")
	    next_phrase.append(" ");
	  next_phrase.append(dictionary[i]);
	  output_phrases.push_back(next_phrase);
	  
	  vector<int> new_letter_freq = letter_freq;
	  for(int j=0;j<dictionary[i].length();++j)
	    new_letter_freq[dictionary[i][j] - 'A']--;

	  findAllPhrases(next_phrase, new_letter_freq, output_phrases, dictionary);
	}
  }
}

int main()
{
	string sArray[12] = {"A", "LIZARD", "ROARS", "GO","RAG", "SOLAR", "DIG", "RAZOR", "RADAR", "GAL", "I", "SIR"};
	vector<string> dict;
	dict.assign(sArray, sArray+12);
	vector<string> output;
	string empty = "";
	string name = "RODRIGO SALAZAR";
	vector<int> freq(26,0);
	for(int i=0;i<name.length();++i) if(name[i] != ' ')
	  freq[name[i] - 'A']++;
	findAllPhrases(empty, freq, output, dict);
	for(int i=0;i<output.size();++i)
	{
	  cout << output[i] << endl;
	}
}