回溯算法
什么是回溯
人生無時不在選擇。在選擇的路口，你該如何抉擇 .....
回溯： 是一種選優搜索法，又稱為試探法，按選優條件向前搜索，以達到目標。但當探索到某一步時，發現原先選擇并不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為“回溯點”。
回溯，計算機算法，回溯法也稱試探法，它的基本思想是：從問題的某一種狀態（初始狀態）出發，搜索從這種狀態出發所能達到的所有“狀態”，當一條路走到“盡頭”的時候（不能再前進），再后退一步或若干步，從另一種可能“狀態”出發，繼續搜索，直到所有的“路徑”（狀態）都試探過。這種不斷“前進”、不斷“回溯”尋找解的方法，就稱作“回溯法”。--百度百科
一個例子看回溯
給下圖的圖頂點進行三種顏色著色（紅、黃、藍)
要求:
每個頂點的顏色只能從紅、黃、藍中選一個種。
相鄰的兩種顏色不能為同一種顏色。
思考方式
暴力推測，查找各種可能...
樹型策略
暴力查找結果(從上向下[第n=1行開始]，從左邊開始):
-
n=1,先取紅，n=2取紅
- [紅、紅、紅], [紅,紅,黃],[紅，紅,藍]; [紅,黃, 紅],[紅，黃，黃]，[紅，黃，藍]；[紅，藍，紅],[紅，藍，黃]，[紅，藍，藍]
-
n=1, n=2取黃
-
n=2, n=3,取藍色
-
回溯到根節點，走n=1，取黃色
回溯的一般規律
我們可以針對以上的找色問題，給出以下的一般的解決方案。
-
初始化： 初始化變量
-
找一個合法值，通過遍歷(+1/-1)選取所有的可能[可以認為是樹的深度]
-
棧記錄
-
遞歸調用
-
回溯已經使用的值
經典題目
全排列
題目
[力扣46] 46. 全排列 - 力扣（LeetCode）
題目描述
給定一個不含重復數字的數組
nums，返回其 所有可能的全排列 。你可以 按任意順序 返回答案。
示例 1：
輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
輸入：nums = [0,1] 輸出：[[0,1],[1,0]]
示例 3：
輸入：nums = [1] 輸出：[[1]]
解決方案
提交模版
public List<List<Integer>> permute(int[] nums) { ? }
參考實現
class Solution {
?private List<List<Integer>> list = new ArrayList<>();private Stack<Integer> stack = new Stack<>();
?public List<List<Integer>> permute(int[] nums) {boolean[] isUsed = new boolean[nums.length];dfs(nums, 0, isUsed);return list;}
?private void dfs(int[] nums, int depth, boolean[] isUsed) {if (depth == nums.length) {list.add(new ArrayList<>(stack));return;}
?for (int i = 0; i < nums.length; i++) {if (isUsed[i]) {continue;}stack.push(nums[i]);isUsed[i] = true;dfs(nums, depth + 1, isUsed);stack.pop();isUsed[i] = false;}}
}全排列II
題目
[力扣47] 47. 全排列 II - 力扣（LeetCode）
題目描述
給定一個可包含重復數字的序列 nums ，按任意順序 返回所有不重復的全排列。
示例 1：
輸入：nums = {1,1,2}
輸出：
{{1,1,2},{1,2,1},{2,1,1}
}
示例 2：
輸入：nums = [1,2,3] 輸出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
解題思路
提交模版
public List<List<Integer>> permuteUnique(int[] nums) { ? }
參考實現
class Solution {private final List<List<Integer>> list = new ArrayList<>();private final Stack<Integer> stack = new Stack<>();private final Set<List<Integer>> sets = new HashSet<>();
?
?public List<List<Integer>> permuteUnique(int[] nums) {boolean[] isUsed = new boolean[nums.length];dfs(nums, 0, isUsed);list.addAll(sets);return list;}
?/*** @param nums* @param depth 遞歸的深度，從底層開始到最后一層* @param isUsed 判斷當前數據是否使用過*/private void dfs(int[] nums, int depth, boolean[] isUsed) {if (depth == nums.length) {sets.add(new ArrayList<>(stack));return;}
?Set<Integer> set = new HashSet<>();//記錄重復數據for (int i = 0; i < nums.length; i++) { //遍歷數組//數據重復或者使用過則跳過當前數據if (isUsed[i] ) continue;// set.add(nums[i]); //記錄選擇的數據// System.out.println("set-->" + set);stack.push(nums[i]);isUsed[i] = true;dfs(nums, depth + 1, isUsed);stack.pop();isUsed[i] = false;}}
}子集問題
題目
[力扣78] 78. 子集 - 力扣（LeetCode）
題目描述
給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。
解集 不能 包含重復的子集。你可以按 任意順序 返回解集。
示例 1：
輸入：nums = [1,2,3] 輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
輸入：nums = [0] 輸出：[[],[0]]
解題思路
創建策略樹
我們會發現出現大量的無效操作數據。對策略樹進行"剪枝"處理。
剪枝- 我們“剪掉”了不滿足約束條件的搜索分支，避免許多無意義的嘗試，從而提高了搜索效率。
提交模版
public List<List<Integer>> subsets(int[] nums) { }
參考實現
class Solution {List<List<Integer>> list = new ArrayList<>();Stack<Integer> stack = new Stack<>();
?public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0);return list;}
?private void dfs(int[] nums, int startIndex) {
?list.add(new ArrayList<>(stack));if (startIndex >= nums.length) {return;}
?for (int i = startIndex; i < nums.length; i++) {stack.push(nums[i]);dfs(nums, i + 1);stack.pop();
?}}
}剪枝優化
class Solution {private final List<List<Integer>> list = new ArrayList<>();private final List<Integer> stack = new ArrayList<>();
?public List<List<Integer>> subsets(int[] nums) {boolean[] isUsed = new boolean[nums.length];dfs(nums, 0, isUsed);return list;}
?private void dfs(int[] nums, int startIndex, boolean[] isUsed) {
?list.add(new ArrayList<>(stack)); //記錄掃描的所有節點for (int i = startIndex; i < nums.length; i++) {if (isUsed[i])continue;stack.add(nums[i]);isUsed[i] = true;dfs(nums, i + 1,isUsed);stack.remove(stack.size()-1);isUsed[i] = false;
?}}
}子集II
題目
[力扣90] 90. 子集 II - 力扣（LeetCode）
)
)
