Efficient ways of generating all sets of pairings of elements in a given array

Let's say I'm given the array {1, 2, 3, 4}, with n (the size of the array) ranging between 2 and 18. I need to find all the ways of arranging these elements pairwise. So for this example, I'd get:

(1, 2), (3, 4)

(1, 3), (2, 4)

(1, 4), (2, 3)

So the order kinda matters here in the sense that I don't want/need to generate all the permutations (I think?) where the pairings are the same. ((1, 2), (3, 4) and (3, 4), (1, 2) for instance.)

I've tried a recursive backtracking approach that kind of works, but it's not really efficient time wise for the larger arrays (14-18), I need an execution time of under 2s for all possible inputs.

Here's my code:

void gen_sol(int k)
{
    if(k > n)
    {
        //do further calculations    
    }
    else
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = i + 1; j <= n; j++)
            {
                if(k == 1)
                {
                    if(!used[i] && !used[j])
                    {
                        sol[k] = v[i];
                        sol[k + 1] = v[j];
                        used[i] = true;
                        used[j] = true;
                        gen_sol(k + 2);
                        used[i] = false;
                        used[j] = false;
                    }
                }
                else
                {
                    if(sol[k - 2] < v[i] && !used[i] && !used[j])
                    {
                        sol[k] = v[i];
                        sol[k + 1] = v[j];
                        used[i] = true;
                        used[j] = true;
                        gen_sol(k + 2);
                        used[i] = false;
                        used[j] = false;
                    }
                }
            }
        }
    }
}

Now I know short, undescriptive names are usually frowned upon, but I don't think this is too bad in a competitive programming context. So k indicates the level of recursion/the current pair I'm working with, sol is the array I'm building the current permutation in and used is used to indicate which elements of the array I've already used.

Regarding the actual pair generation, I'm comparing the current possible pair set to the previous one to see if its lexicographically ordered. I know I could probably merge the 2 separate if statements inside the loops, I should do that.

I've thought about trying an iterative approach, but the execution time for n=18 is just too high with this method anyway, I don't think going iterative would help too much.

Would there be a way to cut down on one loop maybe?