###### tags: `Recursion`
<h1>
Leetcode 17. Letter Combinations of a Phone Number
</h1>
<ol>
<li>問題描述</li>
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.<br><br>

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.<br>


Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

<li>Input的限制</li>
<ul>
<li>0 <= digits.length <= 4</li>
<li>digits[i] is a digit in the range ['2', '9'].</li>
</ul>
<br>

<li>思考流程</li>
<ul>
<li>Backtracking</li>
一個 input 的數字可以轉換成 3~4 個字母，要計算所有字母的組合，其實是個 permutation 問題。直覺上，我們會先固定第一個字母，然後計算所有的組合。依此類推，假設 input 的 digit 是 n，則當我們固定好了 n-1 個字母後，我們會輪流替換最後一個數字對應到的所有字母，來產出所有可能的排列。<br><br>
這個過程像是一個從 root 為空字串出發的 tree，然後到 leaves 的時候會有某一個可能的排序好的字串。<br><br>
我們採用 recursion 的方式來列出所有可能的排序，終止條件為當字串的長度與輸入的 input 長度一樣長，即完成一個要輸出的字串。準備一個串列裝入當前的字母，然後進行下一個 digit 的遞迴呼叫，遞迴整個結束後則移出當前字母，利用 for loop 帶入下一個字母。
<br>
<br>
在時間複雜度的分析上，其窮舉的過程可以列成 T(n) = 3 * T(n-1) + 1 的形式，解出來 time complexity 為 O(4^n)。整個函式會用的空間分為要給 output 的 list 和計算過程中會用到的空間。要給 output 的 list 會涵蓋所有的可能的字串組合，故空間需求為 O(4^n)，計算過程中要用的空間是 recursion 產生的 stack 空間( recursion 每呼叫一次，就會需要儲存當前的參數值、區域變數和返回地址 )，其最大深度為 n，故這個部分需要的空間複雜度是 O(n)。
<br>
<br>
Time Complexity: O(4^n); Space Complexity: O(n) [ 用於 output 的空間不納入計算 ]
<br>
<br>
</ul>
<li>測試</li>
<ul>
<li>test 1</li>
Input: digits = "45" ; Output: ["gj", "gk", "gl", "hj", "hk", "hl", "ij", "ik", "il"]
<li>Invalid input( edge case )</li>
出現0, 1，或是非數字的字元，就印出錯誤訊息。
</ol>