????回溯實(shí)際上就是遍歷的變種，不符合條件時(shí)，本次遍歷向上回退。一般來(lái)說(shuō)，回溯算法都可以將決策路徑畫(huà)成樹(shù)的形狀，成為一棵搜索樹(shù)?；厮莘▓?zhí)行的過(guò)程實(shí)際上就是在這棵樹(shù)上做遍歷。使用回溯法的題目，為什么不能用遞歸法，因?yàn)榛厮莘ㄖ杏涗浡窂降臈Ｖ挥幸粋€(gè)。
1、回溯算法的基本思想
????回溯算法的定義：回溯法采用試錯(cuò)的思想，當(dāng)它通過(guò)嘗試發(fā)現(xiàn)現(xiàn)有的分步答案不能得到有效的正確的解答的時(shí)候，它將取消上一步甚至是上幾步的計(jì)算，再通過(guò)其它的可能的分步解答再次嘗試尋找問(wèn)題的答案。—— 回溯法 - 維基百科[3]
????從字面意思上來(lái)看，回溯（backtracking） 實(shí)際上就是“撤回一步”的意思。而在二叉樹(shù)的 DFS 遍歷中，從一個(gè)結(jié)點(diǎn)退出就是一種回溯?；厮莘ê?DFS 是息息相關(guān)的。
????根據(jù)回溯操作的特性，我們使用棧記錄遍歷時(shí)的當(dāng)前路徑。當(dāng)進(jìn)入一個(gè)結(jié)點(diǎn)時(shí)，做 push 操作；當(dāng)退出一個(gè)結(jié)點(diǎn)時(shí)，做 pop 操作，進(jìn)行回溯。
2、案例1
????給定一個(gè)二叉樹(shù)和一個(gè)目標(biāo)和，找到所有從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑，使得路徑上所有結(jié)點(diǎn)值相加等于目標(biāo)和。
public List<List<Integer>> pathSum(TreeNode root, int sum) {
? ? List<List<Integer>> res = new ArrayList<>();
? ? Deque<Integer> path = new ArrayDeque<>();
? ? traverse(root, sum, path, res);
? ? return res;
}
void traverse(TreeNode root, int sum, Deque<Integer> path, List<List<Integer>> res) {
? ? if (root == null) {
? ? ? ? return;
? ? }
? ? path.addLast(root.val);
? ? if (root.left == null && root.right == null) {
? ? ? ? if (root.val == sum) {
? ? ? ? ? ? res.add(new ArrayList<>(path));
? ? ? ? }
? ? }
? ? int target = sum - root.val;
? ? traverse(root.left, target, path, res);
? ? traverse(root.right, target, path, res);
? ? path.removeLast();
}
????代碼的整體結(jié)構(gòu)和上期例題題解類(lèi)似，只是加上了棧 path 記錄當(dāng)前路徑。關(guān)于棧的 push 和 pop 操作，有兩個(gè)需要注意的地方：
????????????* 保證剛進(jìn)入結(jié)點(diǎn)就 push，最后退出結(jié)點(diǎn)之前才 pop，這樣才能使當(dāng)前路徑和遍歷的進(jìn)度對(duì)應(yīng)；
????????????* 在葉結(jié)點(diǎn)判斷后，不能進(jìn)行 return，否則會(huì)跳過(guò)后面的 pop 操作而出錯(cuò)。
????這兩點(diǎn)都需要做題來(lái)體驗(yàn)，建議親自做一遍例題來(lái)體會(huì)。
3、案例2
? ? 題目：給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
????Subsets 問(wèn)題就是要枚舉出集合的所有子集。生成子集有一個(gè)很簡(jiǎn)單的策略，一個(gè)子集可以選擇使用或不使用第一個(gè)元素，選好之后，再對(duì)第二個(gè)元素進(jìn)行選擇，以此類(lèi)推。這就是一種回溯的思想。這又是一個(gè)樹(shù)的結(jié)構(gòu)。一般來(lái)說(shuō)，回溯算法都可以將決策路徑畫(huà)成樹(shù)的形狀，成為一棵搜索樹(shù)。回溯法執(zhí)行的過(guò)程實(shí)際上就是在這棵樹(shù)上做遍歷。剛好這還是一棵二叉樹(shù)，這又聯(lián)系上了二叉樹(shù)的遍歷。
????那么，我們可以嘗試用遍歷樹(shù)的思路寫(xiě)出回溯法的代碼。這里的棧是當(dāng)前子集里的元素，push 操作是往子集里加元素，pop 操作是從子集中刪除元素（撤銷(xiāo)選擇）。
????最終我們得到完整的代碼：
public List<List<Integer>> subsets(int[] nums) {
? ? Deque<Integer> current = new ArrayDeque<>(nums.length);
? ? List<List<Integer>> res = new ArrayList<>();
? ? backtrack(nums, 0, current, res);
? ? return res;
}
void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {
? ? if (k == nums.length) {
? ? ? ? res.add(new ArrayList<>(current));
? ? ? ? return;
? ? }
? ? // 不選擇第 k 個(gè)元素
? ? backtrack(nums, k+1, current, res);
? ? // 選擇第 k 個(gè)元素
? ? current.addLast(nums[k]);
? ? backtrack(nums, k+1, current, res);
? ? current.removeLast();
}
????這份代碼看起來(lái)和 Path Sum II 的代碼非常類(lèi)似，例如都使用了一個(gè)棧，遞歸的參數(shù)也很像。但是遞歸調(diào)用和 push/pop 的操作方式有一些微妙的地方。
????現(xiàn)在，我們是在調(diào)用遞歸函數(shù)之前和之后進(jìn)行 push/pop，這是因?yàn)閿?shù)組本身并沒(méi)有遞歸結(jié)構(gòu)，我們需要用 push/pop 操作來(lái)營(yíng)造出不同的選擇。兩個(gè)遞歸函數(shù)的調(diào)用其實(shí)都是一樣的，但因?yàn)?current 中的內(nèi)容不一樣，所以其實(shí)是兩個(gè)決策路徑。
4、時(shí)間復(fù)雜度
????回溯算法的復(fù)雜度一般都會(huì)很高。以 Subsets 問(wèn)題為例，從搜索樹(shù)的規(guī)模可以看出算法的時(shí)間復(fù)雜度是非常高的 。不過(guò)，回溯法寫(xiě)成這樣的復(fù)雜度是可接受的，一般的回溯法題目也沒(méi)有更高效的解法。
5、總結(jié)
????通過(guò)這兩個(gè)例題我們看到了回溯算法和二叉樹(shù)遍歷的相似關(guān)系。在求解回溯算法的時(shí)候，我們可以先構(gòu)造一個(gè)搜索樹(shù)，在這個(gè)樹(shù)上遍歷進(jìn)行遞歸求解。
????需要注意的是，例題 Subsets 中的搜索樹(shù)是二叉樹(shù)，這只是個(gè)巧合。實(shí)際上搜索樹(shù)完全可以是多叉樹(shù)，而且多叉樹(shù)才更常見(jiàn)。
????本篇講解的是比較基礎(chǔ)的回溯法思想?；厮莘ㄟ€有很多技巧，例如 Permutation 和 Combination 系列題目，后續(xù)還會(huì)有文章進(jìn)行講解。
6、相關(guān)題目
????二叉樹(shù)遍歷的題目（理解遍歷思想）：
????????????* 129 - Sum Root to Leaf Numbers[4]
????????????* 257 - Binary Tree Paths[5]
????回溯法題目（這里只列出比較簡(jiǎn)單的兩道，更多的題目可以在 LeetCode 上尋找 backtracking 標(biāo)簽）：
????????????* 22 - Generate Parentheses[6]
????????????* 39 - Combination Sum[7]
