組合
給定兩個整數 n 和 k，返回范圍 [1, n] 中所有可能的 k 個數的組合。
示例 1：
輸入：n = 4, k = 2 輸出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
輸入：n = 1, k = 1 輸出：[[1]]
解題思路：DFS
public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res = new ArrayList<>();if (k <= 0 || n < k) {return res;}// 從 1 開始是題目的設定Deque<Integer> path = new ArrayDeque<>();dfs(n, k, 1, path, res);return res;}private void dfs(int n, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {// 遞歸終止條件是：path 的長度等于 kif (path.size() == k) {res.add(new ArrayList<>(path));return;}// 遍歷可能的搜索起點for (int i = begin; i <= n; i++) {// 向路徑變量里添加一個數path.addLast(i);// 下一輪搜索，設置的搜索起點要加 1，因為組合數理不允許出現重復的元素dfs(n, k, i + 1, path, res);// 重點理解這里：深度優先遍歷有回頭的過程，因此遞歸之前做了什么，遞歸之后需要做相同操作的逆向操作path.removeLast();}}
子集
給你一個整數數組 nums ，數組中的元素 互不相同 。返回該數組所有可能的子集（冪集）。解集 不能 包含重復的子集。
示例 1：
輸入：nums = [1,2,3] 輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
輸入：nums = [0] 輸出：[[],[0]]
解題思路：DFS
public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();backtrack(0, nums, res, new ArrayList<Integer>());return res;}private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {res.add(new ArrayList<>(tmp));for (int j = i; j < nums.length; j++) {tmp.add(nums[j]);backtrack(j + 1, nums, res, tmp);tmp.remove(tmp.size() - 1);}}單詞搜索
給定一個 m * n 二維字符網格 board 和一個字符串單詞 word 。如果 word 存在于網格中，返回 true ；否則，返回 false 。
單詞必須按照字母順序，通過相鄰的單元格內的字母構成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個單元格內的字母不允許被重復使用。
示例 1：
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],
word = “ABCCED” 輸出：true
示例 2：
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],
word = “SEE” 輸出：true
示例 3：
輸入：board = [[“A”,“B”,“C”,“E”],[“S”,“F”,“C”,“S”],[“A”,“D”,“E”,“E”]],
word = “ABCB” 輸出：false
public boolean exist(char[][] board, String word) {int h = board.length, w = board[0].length;boolean[][] visited = new boolean[h][w];for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {boolean flag = check(board, visited, i, j, word, 0);if (flag) {return true;}}}return false;}public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {if (board[i][j] != s.charAt(k)) {return false;} else if (k == s.length() - 1) {return true;}visited[i][j] = true;int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};boolean result = false;for (int[] dir : directions) {int newi = i + dir[0], newj = j + dir[1];if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {if (!visited[newi][newj]) {boolean flag = check(board, visited, newi, newj, s, k + 1);if (flag) {result = true;break;}}}}visited[i][j] = false;return result;}刪除有序數組中的重復項2
給你一個有序數組 nums ，請你 原地 刪除重復出現的元素，使得出現次數超過兩次的元素只出現兩次 ，返回刪除后數組的新長度。
示例 1：
輸入：nums = [1,1,1,2,2,3] 輸出：5, nums = [1,1,2,2,3]
示例 2：
輸入：nums = [0,0,1,1,1,1,2,3,3] 輸出：7, nums = [0,0,1,1,2,3,3]
public int removeDuplicates(int[] nums) {int n = nums.length;if (n <= 2) {return n;}int slow = 2, fast = 2;while (fast < n) {if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}搜索旋轉排序數組2
已知存在一個按非降序排列的整數數組 nums ，數組中的值不必互不相同。
在傳遞給函數之前，nums 在預先未知的某個下標 k（0 <= k < nums.length）上進行了 旋轉 ，使數組變為 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下標 從 0 開始 計數）。例如， [0,1,2,4,4,4,5,6,6,7] 在下標 5 處經旋轉后可能變為 [4,5,6,6,7,0,1,2,4,4] 。
給你 旋轉后 的數組 nums 和一個整數 target ，請你編寫一個函數來判斷給定的目標值是否存在于數組中。如果 nums 中存在這個目標值 target ，則返回 true ，否則返回 false 。
示例 1：
輸入：nums = [2,5,6,0,0,1,2], target = 0 輸出：true
示例 2：
輸入：nums = [2,5,6,0,0,1,2], target = 3 輸出：false
public boolean search(int[] nums, int target) {int n = nums.length;if (n == 0) {return false;}if (n == 1) {return nums[0] == target;}int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return true;}if (nums[l] == nums[mid] && nums[mid] == nums[r]) {++l;--r;} else if (nums[l] <= nums[mid]) {if (nums[l] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return false;}
)
