Помогите ускорить алгоритм

Слова выбираешь из массива?
Во первых сделай или двумерный массив или дополнительно еще один, такой же размерности в котором будут логические значения. На использованные слова меняй значение в этом массиве
Во вторых должен быть индекс построенный по принципу бинарного дерева. По нему искать первую букву слова, а затем перебирать слова на эту букву с учетом логического значения.

Алгоритмы полного прямого перебора работают долго и их сложность O(n!).
Посему тебе придется использовать какие-то оптимизированные переборы. Тема большая, сложная, и завязанная на дискретной математике чуть более, чем полностью. Мне это видится так, что на каждом шагу ты должен уметь сделать некую быструю выборку оставшихся слов по указанной букве. Придумывай какие-то сортировки и индексы.
Также здесь можно использовать алгоритм невесты и останавливаться, когда будет достигнут некий минимальный приемлемый критерий, а не делать полный перебор - это в случае, если набор слов не предполагает обязательного наличия полного решения (когда будут использованы все слова).

Сорри, не охота вникать в алгоритм. Просто совет: если хочешь делать быстрые алгоритмы, то научишь засекать время исполнения алгоритма в тактах процессора и обязательно прогоняй алгоритм миллионы раз или для твоего случае всегда думай, что слов будет миллион и будет ли работать тогда алгоритм. Вот для тебя, не важно же какое слово, главное знать начало его и конец, так что все можно упростить

ПМСМ слепить некоторое количество подцепочек, сократив размер множества, а потом их соединять.

сразу вижу ошибку
mass[0] = ' ';
и сразу же
words[i] = strcat(words[i], mass);
mass не null terminated, т. к. malloc не гарантирует заполнение выделенной памяти нулями, на этой строчке возможно всё что угодно (обычно сегфолт)

что касается скорости, то начнём с того, что в худшем случае число всевозможных цепочек увеличивается экспоненциально от количества входных слов, т. е. у тебя временная сложность алгоритма будет о большое от числа данных, которые тебе нужно вывести, в таком случае хотя бы асимптотически особо ничего не поускоряешь

могу только заметить, что find_word вовсе необязательно делать линейной, наверняка можно немного поменять смысл нумерации exsisting_words: пусть слово i заюзано не тогда, когда один из элементов равен i, а тогда, когда i-й элемент больше или равен 0, тогда можно проверять использованность за константу

ну и да, как выше сказали, в случае с небольшим алфавитом можно завести на каждую стартовую букву по списку, в котором хранить все слова на эту букву, в случае несбалансированной/разношерстной выборки слов такое тоже может нехило ускорить процесс (правда, хз причём тут бинарное дерево)

а откуда берёшь данные? Пример исходного массива и начальное слово. Здесь питоновый код хотели переделать на си, но я не взялся. Пупок развязался