# Backtracking in Elixir

How does Backtracking actually work in Elixir? I’m currently working on this leetcode problem where we have been given a string of digits and we have to find all possible letter combinations that the number can represent. However, I can’t seem to understand how backtracking will work here due to immutability of Elixir.

I tried writing my solution based on this C++ code (Solution - II) given below:

``````defmodule Solution do
def letter_combinations(digits) do
ans = []
mappings = %{
"2" => "abc",
"3" => "def",
"4" => "ghi",
"5" => "jkl",
"6" => "mno",
"7" => "pqrs",
"8" => "tuv",
"9" => "wxyz"
}

cond do
String.equivalent?(digits, "") -> ans
true ->
combination = ""
helper(digits, mappings, ans, 0, combination) |> :lists.reverse
end
end

def helper(digits, mappings, ans, i, combi) do
cond do
i == String.length(digits) -> [combi | ans]
true ->
list = mappings[String.at(digits, i)] |> String.graphemes

list |> Enum.reduce({ans, combi}, fn(c, {ans, combi}) ->
combi = combi <> c
ans = helper(digits, mappings, ans, i+1, combi)
combi = String.slice(combi, 0..String.length(combi)-1) # Backtracking

{ans, combi}
end)
|> elem(0)
end
end
end

digits ="23"
IO.inspect Solution.letter_combinations(digits)
``````

What I’m doing here is creating `mappings` that maps the phone digits with the corresponding alphabets. Then, inside the `helper` function, I check to see if the variable `i` is equal to the size of the string (in this case, we will return `ans` since our condition has been met).

Then, I extract the graphemes from the map using the digits string as the key and then apply reduce over it. Inside the reduce, I concatenate the letter combinations and then update my `ans` list along with the backtracking process.

However, my results don’t seem to be accurate and I seem to be getting the output `["ad", "ade", "adef", "abd", "abde", "abdef", "abcd", "abcde", "abcdef"]` when it should be `["ad","ae","af","bd","be","bf","cd","ce","cf"]`.

Can someone guide me as to what am I doing wrong here? Also, for general purposes, how can we perform backtracking in Elixir if it is possible?

Any help will be appreciated. Thank you!

This doesn’t shorten `combi` - it takes the whole thing. You’d need to subtract 2 instead of 1 to get the result you expect.

HOWEVER

A better way to do it is to not rebind `combi`:

``````                list |> Enum.reduce({ans, combi}, fn(c, {ans, combi}) ->
longer_combi = combi <> c
ans = helper(digits, mappings, ans, i+1, longer_combi)

{ans, combi}
end)
``````

You do not need backtracking, all you need is to notice, that `<<c>> <> rest` is the result of:

``````Enum.map(keypad_characters[c], &[&1 | letter_combinations(rest)])
``````

Aka, the mapping of the first character of the string with combinations of rest of the characters.

Here you have my solution:

``````defmodule Solution do
@letters %{
?2 => 'abc',
?3 => 'def',
?4 => 'ghi',
?5 => 'jkl',
?6 => 'mno',
?7 => 'pqrs',
?8 => 'tuv',
?9 => 'wxyz'
}

@spec letter_combinations(digits :: String.t) :: [String.t]
def letter_combinations(<<>>), do: []
def letter_combinations(str), do: do_letter_combinations(str)

defp do_letter_combinations(""), do: [""]

defp do_letter_combinations(<<c>> <> rest) do
for l <- @letters[c],
suffix <- do_letter_combinations(rest),
do: <<l>> <> suffix
end
end
``````

Some additional logic is needed to simplify the the above statement, but in general it is all that is needed.

2 Likes

here’s a solution with reduce (which always solves all otherwise unsolvable problems).

``````defmodule Phone do
@keys %{
2 => 'abc',
3 => 'def',
4 => 'ghi',
5 => 'jkl',
6 => 'mno',
7 => 'pqrs',
8 => 'tuv',
9 => 'wxyz'
}

def letter_combinations([]), do: []

def letter_combinations([digit | digits]) do
Enum.reduce(
digits,
Enum.map(@keys[digit], &[&1]),
fn digit, acc -> for i <- acc, j <- @keys[digit], do: i ++ [j] end
)
end
end
``````

Oneliner, fwiw. Change `"23"` to the desired input.

``````# thanks Hauleth for letters I stole from your solution :)
letters = %{
?2 => 'abc',
?3 => 'def',
?4 => 'ghi',
?5 => 'jkl',
?6 => 'mno',
?7 => 'pqrs',
?8 => 'tuv',
?9 => 'wxyz'
}

for <<c <- "23">>, reduce: [] do
[] -> letters[c]
acc -> Enum.flat_map(acc, fn e -> (for l <- letters[c], do: List.wrap(e) ++ [l]) end)
end
#⇒ ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
``````
3 Likes