LeetCode46全排列(回溯入門)
2023-09-01 09:00:31
歡迎存取我的GitHub
這裡分類和彙總了欣宸的全部原創(含配套原始碼)：https://github.com/zq2599/blog_demos
題目描述
-
難度：中等
-
給定一個不含重複數位的陣列
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]]
個人回溯和46題的理解
-
在很多刷題文章和書籍中，此題都被用做回溯演演算法的第一題，可見該題很有代表性，搞定此題意味著對回溯有了最基本的瞭解，當然就個人感受而言，以此作為回溯的第一題弊端也不小：本以為掌握了基本套路，刷其他回溯題的時候套上去即可，結果後來發下一道題都套不成功...
-
套不成功？是因為此題沒有代表性嗎？當然不是，這是道典型的回溯演演算法題，但個人的感覺是：解題的關鍵不是套用模板，而是對回溯思想的理解，我個人的理解是：深度至上
-
所謂深度至上，就是弄清楚在當前深度能做什麼，例如46題全排列，一個深度意味著可選數位中做了一輪選擇，每選中一個，都牢牢佔據這一層的固定位置，下面的子樹都要有他
-
只要理解了深度至上，就清楚在當前做任何事情的時候都要確保深度固定，下圖是[1,2]兩個數位全排列的手繪圖，邊上數位表示選擇，方框中的數位表示選擇後的結果，請看藍色框，在選擇2的時候，要牢記當深度只能有一個數位，於是，剛才選擇1的時候記錄存在路徑中的1就要果斷刪除，牢記當前層應該佔據哪個位置，回溯的效果就有了
解題思路
-
要用回溯演演算法解此題，有幾個關鍵要注意
-
全排列，意味著相同數位只要排列不同，也能算作結果的一種
-
雖然不推薦用模板去套，但回溯該有的幾個核心概念還是不能少的：
-
終止條件：只要組合的數位達到給定數位的長度，就可以終止了
-
路徑：就是正在組合的元素，可以用陣列表達
- 此外還要有個輔助引數，用於記錄那些值不能參與組合，以上圖為例，在藍色那一層如果選擇了1，那麼在下一層就不能再選擇1了，所以在組合的時候，要有地方可以查到1不可用
編碼
- 接下來可以寫程式碼了，如下，有幾處要注意的地方稍後會提到
public class L0046 {
List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
// 回溯過程中的重要輔助引數：標記nums陣列中有哪些已經使用過
boolean[] used = new boolean[nums.length];
// 回溯過程中的重要輔助引數：路徑
int[] path = new int[nums.length];
dfs(nums, used, path, 0);
return res;
}
public void dfs(int[] nums, boolean[] used, int[] path, int depth) {
// 終止條件(深度達到)
// 蒐集：棧入res
// 本題的終止條件是一次組合的長度達到陣列長度
if (depth==nums.length) {
// 蒐集結果
// 千萬注意：這個path一直在使用中，所以不能把path放入res中，而是path的元素
// res.add(Arrays.stream(path).boxed().collect(Collectors.toList()));
List<Integer> list = new ArrayList<>();
for(int val : path) {
list.add(val);
}
res.add(list);
return;
}
// for迴圈
for (int i=0;i<nums.length;i++) {
// 如果當前數位沒有用到，就標記，進入path，再做dfs
if (!used[i]) {
used[i] = true;
// 注意，path的下標千萬不要用i！
// 例如1和2的全排列，在製造[2,1]的時候，i=1，但此時要修改的是path[i]，
// 所以path的下標應該是depth
path[depth] = nums[i];
// 一次遞迴，深度要加一
dfs(nums, used, path, depth+1);
used[i] = false;
}
}
}
public static void main(String[] args) {
List<List<Integer>> list = new L0046().permute(new int[] {1,2,3});
list.forEach(one -> {
Tools.printOneLine(one);
});
}
}
- 上述程式碼有以下幾處要注意
- res用於蒐集達到終止條件的記錄，也就是數位組合結果
- dfs方法就是本次回溯操作的核心方法
- 下圖紅色箭頭所指程式碼就是本題最重要的一行，可見for迴圈的執行過程中，修改的都是path陣列的同一個位置的值，這就是剛才提到的深度至上，只有進入了下面的dfs方法後，深度變化，修改的path陣列的位置才會發生變化
- used陣列用來記錄深度呼叫過程中，那些數位已經被使用了，當前不要再使用
- 很多回溯的程式碼中，用棧物件保持path中的資料，入棧push，出棧pop都是標準操作，但是本題中用char陣列，再配合depth，就可以滿足需要了，這種原始型別的使用也會帶來更好的效能
執行結果
- 寫完程式碼提交，執行結果如下，超過100.00%的提交
- 至此，回溯入門實戰已經完成，此時需要強烈提示：程式碼中那個for迴圈，在每一層都遍歷nums的所有元素，那是此題的特殊操作，千萬不要以為是模板或者套路，其他回溯題中，不會像此題這樣每一層都遍歷的