思想
回溯法（back tracking）（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索雷恃，以達到目標。但當探索到某一步時费坊，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標倒槐，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法附井，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”讨越。
回溯法解求解問題步驟
- 針對給定問題，定義問題的解空間樹永毅；（這一步非常重要０芽纭！）
- 確定易于搜索的解空間結構沼死；
- 以深度優(yōu)先方式搜索解空間着逐，并且在搜索過程中用剪枝函數(shù)避免無效搜索；
- 用回溯法求解問題意蛀，重點是設計問題的解空間樹耸别，其解題過程則是深度遍歷解空間樹的過程。
注：在回溯法中通常會使用到“遞歸”和“剪枝”
常用的剪枝函數(shù)：用約束函數(shù)在擴展結點處剪去不滿足約束的子樹浸间；用限界函數(shù)剪去得不到最優(yōu)解的子樹太雨。
回溯法對解空間做深度優(yōu)先搜索時，有遞歸回溯和迭代回溯（非遞歸）兩種方法魁蒜，但一般情況下用遞歸方法實現(xiàn)回溯法囊扳。
模板
回溯法的一般模板，可以如下所示：
demoMethod() {
//生成回溯結果的存儲位置
Object res = new Object();
//邊界值判定兜看，比如n == 0之類的锥咸。
if() return res;
//回溯遞歸函數(shù)，先寫出來占個坑细移，參數(shù)一會兒加搏予。
backTrack();
//返回，程序結束弧轧。
return res;
}
backTrack(...args[]) { //參數(shù)根據(jù)題目實際情況來定雪侥，數(shù)量一般會在4-5個左右
// 遞歸的結束條件
if () {
}
//回溯算法的主體碗殷，包括前進和回溯，sub是存儲結果
for(){
add() // 1.一個解中的某個元素速缨，進行添加;
backTrack(index + 1); // 2.進行深搜锌妻，進行到解空間樹的下一層
sub.remove(sub.size() - 1); // 3.*回溯到解空間樹的上一層
}
}
需要注意的是：
- for循環(huán)的次數(shù)；：在解空間樹種每一層有多少種可能的答案旬牲，就要循環(huán)多少次仿粹。
- 以及遞歸的結束條件：當達到解空間樹的葉子節(jié)點，即遞歸的結束條件一般會跟解空間樹的深度有關原茅。
具體我們以下面的例子做講解：
例子
Leetcode上有很多回溯算法問題吭历。這里用一個leetcode上比較經(jīng)典的題目來做示例
傳送門：https://leetcode-cn.com/problems/permutations-ii/
下面將詳細介紹一下解題思路：（此思路適用回溯法80%的題目）：
1.定義問題的解空間樹，如下圖所示擂橘；
2.分析發(fā)現(xiàn)晌区，在回溯函數(shù)中循環(huán)的次數(shù)應該是每次剩下數(shù)組的長度（因為每次都會存儲一個值）；如下圖中橫框框住的元素個數(shù)贝室，第一層3種情況契讲；第二層2種情況；第三層1種情況滑频；
3.遞歸結束條件：當當前的解中的元素經(jīng)滿了（即3個，給定的數(shù)組的長度）唤冈，則跳出本層峡迷，回到上層樹。
值得注意的是：本題有個要求是你虹，答案不能有重復的绘搞。如果不進行剪枝，則會有6個答案傅物，但是如圖所示有兩處可以剪枝夯辖，那剪枝的條件是什么呢？我們發(fā)現(xiàn)董饰，只要在每層訪問的時候蒿褂，如果這個節(jié)點我們已經(jīng)訪問過了，我們就可以直接跳過卒暂，例如：在第一層啄栓，第二個的1已經(jīng)訪問過，所以我們可以跳過也祠。因此我們可以在每一層都維護一個已經(jīng)訪問的節(jié)點即可昙楚。
解答
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> deque = new LinkedList<>();
if (nums.length == 0) {
return res;
}
for (int i = 0; i < nums.length; i++) {
deque.add(nums[i]);
}
backTrack(res, new ArrayList<>(), deque, nums.length);
return res;
}
/**
*
* @param res - 存儲最后的結果，即返回值
* @param curList - 存儲當前的值
* @param deque - 解空間樹種每一層可能的情況的集合
* @param length - 遞歸結束條件的長度诈嘿，即樹的深度
*/
private static void backTrack(List<List<Integer>> res, List<Integer> curList, List<Integer> deque, int length) {
if (curList.size() == length) {
res.add(new ArrayList<>(curList));
}
int size = deque.size();
List<Integer> visited = new ArrayList<>();
for (int i = 0; i < size; i++) {
// 剪枝函數(shù)
if (visited.contains(deque.get(i))) {
continue;
}
visited.add(deque.get(i));
List<Integer> temp = new ArrayList<>(deque);
curList.add(deque.get(i));
temp.remove(i);
backTrack(res, curList, temp, length);
curList.remove(curList.size() - 1);
}
}
}
