Solution
Approach 1: Backtracking
Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.
Here is a backtrack function backtrack(combination, next_digits)
which takes as arguments an ongoing letter combination
and the next digits to check.
 If there is no more digits to check that means that the current combination is done.
 If there are still digits to check :
 Iterate over the letters mapping the next available digit.
 Append the current letter to the current combination
combination = combination + letter
.  Proceed to check next digits :
backtrack(combination + letter, next_digits[1:])
.
 Append the current letter to the current combination
 Iterate over the letters mapping the next available digit.
!?!../Documents/17_LIS.json:1000,592!?!
Complexity Analysis

Time complexity : where
N
is the number of digits in the input that maps to 3 letters (e.g.2, 3, 4, 5, 6, 8
) andM
is the number of digits in the input that maps to 4 letters (e.g.7, 9
), andN+M
is the total number digits in the input. 
Space complexity : since one has to keep solutions.