Generate combinations by combining adjacent characters

I have a program that should generate combinations of concatenation of all possible adjacent characters.

For example

Input = [a,b,c]
Output = [a,b,c], [ab,c], [a,bc]

Input = [a,b,c,d]
Output = [a,b,c,d], [ab,c,d], [a,bc,d], [a,b,cd], [ab,cd]

Input = [a,b,c,d,e]
Output = [a,b,c,d,e], [ab,c,d,e], [a,bc,d,e], [a,b,cd,e], [a,b,c,de], [ab,cd,e], [a,bc,de], **[ab,c,de]**
Last one missing from my program output

Basically we are only allowed to combine two adjacent characters.

I have written the program below.

public class Program
{
    public static void Main(string[] args)
    {
        List<string> cases = new List<string> {"a b c", "a b c d", "a b c d e"};
        for (int c = 0; c < cases.Count; c++)
        {
            var result = F(cases[c]);
            Console.WriteLine(cases[c]);
            result.ForEach(Console.WriteLine);
            Console.WriteLine("---------------------------");
        }
    }

    public static List<string> F(string searchTerm)
    {
        List<string> result = new List<string>();
        var terms = searchTerm.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).ToList();
        if (terms.Count == 1)
            return new List<string> { searchTerm };

        for (int x = 1; x <= 2; x++)
        {
            for (int i = 0; i < terms.Count - 1; i++)
            {
                if (x == 1)
                {
                    int j = i;
                    var joinedWord = terms[j] + terms[j + 1];
                    result.Add(searchTerm.Replace($"{terms[j]} {terms[j + 1]}", joinedWord));
                }

                if (x == 2)
                {
                    int j = i;
                    if (j + 3 < terms.Count)
                    {
                        var firstJoinedWord = terms[j] + terms[j + 1];
                        var secondJoinedWord = terms[j + 2] + terms[j + 3];
                        result.Add(searchTerm.Replace($"{terms[j]} {terms[j + 1]} {terms[j + 2]} {terms[j + 3]}", firstJoinedWord + " " + secondJoinedWord));
                    }
                }
            }
        }
        

        return result;
    }
}

And here is the output.

I don't know if we need to use Recursion/Dynamic Programming to solve this? because there can be N number of combinations. Any help will be appreciated. Thanks.

Check out this code

arr = ["a", "b", "c", "d", "e"]


possibilities = []

def generate_combinations(combination, index):
    global arr
    if index == len(arr):
        possibilities.append(list(combination))
    else:
        # Either we can concatenate with our adjacent
        if index < len(arr) - 1:
            generate_combinations(combination + [arr[index] + arr[index+1]], index+2)
        # Or we don't
        generate_combinations(combination + [arr[index]], index+1)

generate_combinations([], 0)


for p in possibilities:
    print(p)

Output for your test case:

['ab', 'cd', 'e']
['ab', 'c', 'de']
['ab', 'c', 'd', 'e']
['a', 'bc', 'de']
['a', 'bc', 'd', 'e']
['a', 'b', 'cd', 'e']
['a', 'b', 'c', 'de']
['a', 'b', 'c', 'd', 'e']
[Finished in 40ms]

Let me know if the solution isn't understandable

Here's a quick JavaScript version that you can run in your browser to verify the result -

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function *mates(t) {
  if (t.length == 0) return yield []
  if (t.length == 1) return yield t
  for (const m of mates(t.slice(1)))
    yield [t[0], ...m]
  for (const m of mates(t.slice(2)))
    yield [mate(t[0], t[1]), ...m]
}

function mate(a,b) {
  return a + b
}

for (const m of mates(["a", "b", "c", "d", "e"]))
  console.log(m.join(","))

<!-- language: lang-css -->

.as-console-wrapper { min-height: 100%; top: 0; }

<!-- end snippet -->

a,b,c,d,e
a,b,c,de
a,b,cd,e
a,bc,d,e
a,bc,de
ab,c,d,e
ab,c,de
ab,cd,e

We can easily convert that to a C# program -

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    public static IEnumerable<List<string>> Mates(List<string> t)
    {
        if (t.Count == 0)
        {
            yield return new List<string> {};
            yield break;
        }
    
        if (t.Count == 1)
        {
            yield return t;
            yield break;
        }
        
        foreach (var m in Mates(t.GetRange(1, t.Count - 1)))
            yield return new List<string> { t[0] }
                .Concat(m)
                .ToList();
        
        foreach (var m in Mates(t.GetRange(2, t.Count - 2)))
            yield return new List<string> { Mate(t[0], t[1]) }
                .Concat(m)
                .ToList();
    }
    
    public static string Mate(string a, string b)
    {
        return a + b;
    }
    
    public static void Main(string[] args)
    {
        var input = new List<string> { "a", "b", "c", "d", "e" };
        
        foreach (var m in Mates(input))
            Console.WriteLine(string.Join(",", m));
    }
}

a,b,c,d,e
a,b,c,de
a,b,cd,e
a,bc,d,e
a,bc,de
ab,c,d,e
ab,c,de
ab,cd,e