Consonants and vowels

Go to the Jutge statement of the problem

Write a program that reads n consonants and n vowels, and prints all the words that can be made up by using each letter exactly once. The words must begin with a consonant, and alternate consonants and vowels. In this exercise, we will assume that y is a vowel.

Input: Input consists of a natural number n between 1 and 6, followed by n different consonants and n different vowels. Both consonants and vowels are given in alphabetical order.

Output: Print the words that can be made up with the 2n given letters, starting with a consonant and always alternating consonants and vowels. Print the words in alphabetical order, one per line.

Hint

Use the usual template for backtracking.

Be careful on odd and even indices.

A possible C++ code to start the problem

// Consonants and vowels
#include<iostream>
#include<vector>
#include<string>

using namespace std;
using VVB = vector<vector<bool>>;
using VB = vector<bool>;

const int CONSONANTS = 0;
const int VOWELS = 1;

void backtrack(string& sol, int k, const vector<string>& letters, VVB& used){
   // put code here
}

int main(){
    int n;
    cin >> n;
    vector<string> letters(2); 
    cin >> letters[CONSONANTS] >> letters[VOWELS];
    string sol = string(2*n, ' ');
    VVB used(2, VB(n, false));
    backtrack(sol, 0, letters, used);
}

A possible solution

// Consonants and vowels
#include<iostream>
#include<vector>
#include<string>

using namespace std;
using VVB = vector<vector<bool>>;
using VB = vector<bool>;

const int CONSONANTS = 0;
const int VOWELS = 1;

void backtrack(string& sol, int k, const vector<string>& letters, VVB& used){
    int m = sol.size();
    if (k == m) cout << sol << endl;
    else{
        int k2 = k%2;
        for(int i = 0; i < m/2; ++i)
            if (not used[k2][i]){
                sol[k] = letters[k2][i];
                used[k2][i] = true;
                backtrack(sol, k+1, letters, used);
                used[k2][i] = false;
            }
    }
}

int main(){
    int n;
    cin >> n;
    vector<string> letters(2); 
    cin >> letters[CONSONANTS] >> letters[VOWELS];
    string sol = string(2*n, ' ');
    VVB used(2, VB(n, false));
    backtrack(sol, 0, letters, used);
}