一、組合
參考鏈接77. 組合 - 力扣（LeetCode）
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<Integer>> combine (int n, int k) {List<List<Integer>> res = new ArrayList<>();if (k <= 0 || n < k) {return res;}Deque<Integer> path = new ArrayDeque<>();dfs(n, k, 1, path, res);return res;}private void dfs(int n, int k, int index, Deque<Integer> path, List<List<Integer>> res) {//如果當前path的大小和 k相等，則將結果保存到ArrayList當中if (path.size() == k) {res.add(new ArrayList<>(path));return;}// 剪枝優化 i <= n - (k - path.size()) + 1 背吧，歸納法for (int i = index; i <= n - (k - path.size()) + 1; i++) {path.addLast(i);dfs(n, k, i + 1, path, res);path.removeLast();}}
}
二、遞增子序列
核心理解：set去重
set在dfs的實現的方式是 new HashSet<>()，而不是在函數外定義的set，每一次遞歸都會生成新的Set，
class Solution {// 定義全局變量保存結果List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {// idx 初始化為 -1，開始 dfs 搜索。dfs(nums, -1, new ArrayList<>());return res;}private void dfs(int[] nums, int idx, List<Integer> curList) {// 只要當前的遞增序列長度大于 1，就加入到結果 res 中，然后繼續搜索遞增序列的下一個值。if (curList.size() > 1) {res.add(new ArrayList<>(curList));}// 在 [idx + 1, nums.length - 1] 范圍內遍歷搜索遞增序列的下一個值。// 借助 set 對 [idx + 1, nums.length - 1] 范圍內的數去重。
//注意 set是 數中每一層的 變量，到達下一層時又new了HashSetSet<Integer> set = new HashSet<>();for (int i = idx + 1; i < nums.length; i++) {// 1. 如果 set 中已經有與 nums[i] 相同的值了，說明加上 nums[i] 后的所有可能的遞增序列之前已經被搜過一遍了，因此停止繼續搜索。if (set.contains(nums[i])) { continue;}set.add(nums[i]);// 2. 如果 nums[i] >= nums[idx] 的話，說明出現了新的遞增序列，因此繼續 dfs 搜索（因為 curList 在這里是復用的，因此別忘了 remove 哦）if (idx == -1 || nums[i] >= nums[idx]) {curList.add(nums[i]);dfs(nums, i, curList);curList.remove(curList.size() - 1);}}}
}
- 比如 4 7 3 2 1 7 … 這個數組，當curList遍歷到 4 7 的時候，進入遞歸，一直遍歷直到 出現 第二個7，這時候出現了 4 7 7 序列添加到結果中
- 回溯到 4 7 ，在當前層的for循環進行遍歷，再次遍歷到 第二個 7，判斷set中有7，通過1我們知道 4 7 7 開頭的數組組合我們在遞歸中已經將其實現，所以這一枝我們進行剪枝
- 回歸set的作用，處理數組中出現相同值時 出現重復結果(也就是去重)
參考鏈接46. 全排列 - 力扣（LeetCode）
三、全排列
import java.util.ArrayList;
import java.util.List;public class Solution {public List<List<Integer>> permute(int[] nums) {int len = nums.length;// 使用一個動態數組保存所有可能的全排列List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}//使用一個數組表示某個數是否已經被選過，選過為true，否則為falseboolean[] used = new boolean[len];List<Integer> path = new ArrayList<>();dfs(nums, len, 0, path, used, res);return res;}
//nums 當前數組，len 數組長度，depth表示深度，path 當前走過的路徑，used 某個數字是否被選中， res 結果數組private void dfs(int[] nums, int len, int depth,List<Integer> path, boolean[] used,List<List<Integer>> res) {
// 如果遍歷到 深度 和 長度 相等表示所有數字都已經被選擇過了if (depth == len) {res.add(path);return;}// 在非葉子結點處，產生不同的分支，這一操作的語義是：在還未選擇的數中依次選擇一個元素作為下一個位置的元素，這顯然得通過一個循環實現。 ****這段是重點核心代碼，需要背for (int i = 0; i < len; i++) {if (!used[i]) {path.add(nums[i]);used[i] = true;dfs(nums, len, depth + 1, path, used, res);// 注意：下面這兩行代碼發生 「回溯」，回溯發生在從 深層結點 回到 淺層結點 的過程，代碼在形式上和遞歸之前是對稱的used[i] = false;path.remove(path.size() - 1);}}}public static void main(String[] args) {int[] nums = {1, 2, 3};Solution solution = new Solution();List<List<Integer>> lists = solution.permute(nums);System.out.println(lists);}
}
四、全排列2
使用存在重復數字的數組來生成新的全排列數組，要求去重
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<Integer>> permuteUnique(int[] nums) {int len = nums.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}// 排序（升序或者降序都可以），排序是剪枝的前提Arrays.sort(nums);boolean[] used = new boolean[len];// 使用 Deque 是 Java 官方 Stack 類的建議Deque<Integer> path = new ArrayDeque<>(len);dfs(nums, len, 0, used, path, res);return res;}private void dfs(int[] nums, int len, int depth, boolean[] used, Deque<Integer> path, List<List<Integer>> res) {if (depth == len) {res.add(new ArrayList<>(path));return;}for (int i = 0; i < len; ++i) {if (used[i]) {continue;}// 剪枝條件：i > 0 是為了保證 nums[i - 1] 有意義// 寫 !used[i - 1] 是因為 nums[i - 1] 在深度優先遍歷的過程中剛剛被撤銷選擇，被撤銷選擇為falseif (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {continue;}path.addLast(nums[i]);used[i] = true;dfs(nums, len, depth + 1, used, path, res);// 回溯部分的代碼，和 dfs 之前的代碼是對稱的used[i] = false;path.removeLast();}}
}A 1分24秒到2分00秒：講了為什么要先排序 因為結果是要去重的，而結果都是列表形式的，那列表怎么判重呢？就是排序之后一個一個的比較，所以那還不如先排序之后再計算，在計算的過程中判斷是否有重復，免得對每個結果再做一次排序去重操作。再一個，排序之后相同的元素一定重復嗎？不一定，不同結果經過排序之后也可能相同
B 為什么" nums[i-1] 的used狀態是被選擇的，那么說明當前的nums[i] 是 nums[i-1]的下一層路徑。"
原因：因為往下層遞歸的話，一直再往下層走，dfs還未return，也就是說used還沒有被回溯為未選擇狀態，所以同一條分支上，nums[i-1] 的used狀態一定是被選擇的。
為什么“ 如果 nums[i-1] 的狀態是沒被選擇的，那么說明當前 的nums[i] 是nums[i-1] 同層路徑。”
原因：遞歸到葉節點，開始往上回溯了，回溯到某一層時把used[i-1]回溯為未選擇狀態，然后for循環i++橫向移動，自然這時再判斷used[i-1]就一定是未選擇狀態。
)
