回溯.md

关于回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

---

回溯算法实例

下面列举回溯算法实例

[LeetCode]17. 电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/description/

将按键的每个字符尝试连接起来，相当于列举出所有满足条件的答案

    public IList<string> LetterCombinations (string digits) {
        List<string> result = new List<string> ();
        if (digits.Length == 0) {
            return result;
        }
        Dictionary<char, string> dic = new Dictionary<char, string> ();
        dic['2'] = "abc";
        dic['3'] = "def";
        dic['4'] = "ghi";
        dic['5'] = "jkl";

        dic['6'] = "mno";
        dic['7'] = "pqrs";
        dic['8'] = "tuv";
        dic['9'] = "wxyz";
        backTrack (0, dic, digits, "", result);
        return result;
    }

    private void backTrack (int index, Dictionary<char, string> dictionary, string digits, string str, List<string> result) {
        if (str.Length == digits.Length) {
            result.Add (str);
        } else {
            string s = dictionary[digits[index]];
            for (int i = 0; i < s.Length; i++) {
                str += s[i];
                backTrack (index + 1, dictionary, digits, str, result);
                str = str.Remove (str.Length - 1);
            }
        }
    }

https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html