組合I?

class Solution {List<List<Integer>> result = new ArrayList(); // 所有結果集List<Integer> list = new ArrayList(); // 當前結果集public List<List<Integer>> combine(int n, int k) {dfs(n, k, 1);return result;}public void dfs(int n, int k, int index) {if (list.size() == k) { // 當前結果集等于要收集的數量即可存入最終結果集List<Integer> tem = new ArrayList(list);result.add(tem);return;}for (int i = index; i <= n; i++) {list.add(i); // 元素加入當前結果集dfs(n, k, i + 1); // 遞歸list.remove(list.size() - 1); // 該元素組合完成可以移除（回溯）}}
}

組合II?

class Solution {List<List<Integer>> result = new ArrayList(); // 所有結果集Set<List<Integer>> set = new HashSet(); // 結果集去重List<Integer> list = new ArrayList(); // 當前結果集public List<List<Integer>> combinationSum2(int[] candidates, int target) {backTring(candidates, 0, target, 0);return result;}public void backTring(int[] candidates, int sum, int target, int index) {if (candidates == null || candidates.length < 0) return; if (sum == target) { // 總和等于目標值是返回當前結果集List<Integer> tem = new ArrayList(list);Collections.sort(tem); // 去重（如：1 1 2 和 2 1 1 是一組結果集）if (!set.contains(tem)) { result.add(new ArrayList(list));set.add(tem);}return;}if (sum > target) { // 當前結果集大于目標值說明當前結果集不對return;}for (int i = index; i < candidates.length; i++) {sum += candidates[i]; // 當前總和list.add(candidates[i]); // 當前結果集backTring(candidates, sum, target, i + 1);sum -= candidates[i]; // 回溯總和list.remove(list.size() - 1); // 回溯結果集}}
}

?組合III

class Solution {List<List<Integer>> result = new ArrayList(); // 最終結果集List<Integer> list = new ArrayList(); // 當前結果集public List<List<Integer>> combinationSum3(int k, int n) {backCheck(k, n, 1, 0, 0);return result;}public void backCheck(int k, int n, int num, int count, int sum) {if (count == k && n == sum) { // 元素數量等于k 且 sum等于 n 時為符合的結果集result.add(new ArrayList(list));return;}if (count > k || n < sum) { // 要求的數量或者總和不對則返回return;}for (int i = num; i <= 9; i++) {list.add(i);sum += i;count++;backCheck(k, n, i + 1, count, sum);list.remove(list.size() - 1);sum -= i;count--;}}
}

?分割回文串

class Solution {List<List<String>> result = new ArrayList(); // 最終結果集List<String> list = new ArrayList(); // 當前結果集public String[][] partition(String s) {int n = s.length();dfs(0, n, s);return listToArrays(result); // 集合轉換為數組}public void dfs(int index, int n, String s) {if (index == n) { // 指針指向n時說明遍歷到字符串末尾，可以返回結果集result.add(new ArrayList(list));return;}for (int i = index; i < n; i++) {if (isPalindrome(s.substring(index, i + 1))) {  // 如果是回文串則加入當前結果集         list.add(s.substring(index, i + 1)); // 加入結果集dfs(i + 1, n, s);list.remove(list.size() - 1); // 回溯}}}public boolean isPalindrome(String str) { // 判斷是否為回文串int l = 0;int r = str.length() - 1;while (l < r) {if (str.charAt(l) != str.charAt(r)) {return false;}l++;r--;}return true;}public String[][] listToArrays (List<List<String>> list) { // 集合轉換為數組int n = list.size();String[][] arrs = new String[n][];for (int i = 0; i < n; i++) {List<String> tem = list.get(i);String[] arr = tem.toArray(new String[tem.size()]);arrs[i] = arr;}return arrs;}
}

復原 IP 地址

class Solution {List<String> res = new ArrayList(); // 所有結果集List<String> tem = new ArrayList(); // 當前結果集public List<String> restoreIpAddresses(String s) {int n = s.length(); // 字符串長度if (n < 0 || n > 12) return res; // 剪枝dfs(s, 0, n);return res;}public void dfs(String s, int index, int n) {if (tem.size() == 4) { // ip地址為四個數字組成，當前結果集等于4即可返回if (index == n) { // 當前指針指向末尾即可加入最終結果集StringBuilder sb = new StringBuilder(); // 拼湊成需要的字符串for (int i = 0; i < 4; i++) {sb.append(tem.get(i));if (i != 3) {sb.append(".");}}res.add(sb.toString()); // 加入到最終結果集}return;}for (int i = index; i < n && i < index + 3; i++) { // 當前指針if (isNum(s.substring(index, i + 1))) { //tem.add(s.substring(index, i + 1));dfs(s, i + 1, n);tem.remove(tem.size() - 1);}}}public boolean isNum(String s) { // 判斷是否為合法數字if (s.length() >= 2 && s.charAt(0) == '0') return false;Integer num = Integer.valueOf(s);if (num > 255) return false;return true;}
}

子集I

class Solution {List<List<Integer>> res = new ArrayList();List<Integer> tem = new ArrayList();public List<List<Integer>> subsets(int[] nums) {dfs(nums, 0, nums.length);return res;}public void dfs(int[] nums, int index, int n) {res.add(new ArrayList(tem)); // 每次遞歸都是一個新子集for (int i = index; i < n; i++) {tem.add(nums[i]);dfs(nums, i + 1, n);tem.remove(tem.size() - 1);}}
}

?子集II

class Solution {List<List<Integer>> res = new ArrayList(); // 所有結果集List<Integer> list = new ArrayList(); // 當前子集Set<List<Integer>> set = new HashSet();  // 子集去重public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums); // 排序dfs(nums, 0, nums.length);return res;}public void dfs(int[] nums, int index, int n) {res.add(new ArrayList(list)); // 每次遞歸都是新子集for (int i = index; i < n; i++) {if (i != index && nums[i] == nums[i - 1]) continue; // 數組已經排序，如果當前元素等于上一個元素進行遞歸會有重復子集（如：數組 {1 1} 的子集為 {1} {1 1}，如果索引到第二個元素再進行遞歸則會有重復子集{1}list.add(nums[i]); dfs(nums, i + 1, n);list.remove(list.size() - 1);}}
}

?最長遞增子序列

?

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length]; // 動態規劃+暴力枚舉Arrays.fill(dp, 1); // 每個子序列起始都是1int max = dp[0];for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) { // 判斷當前位置最長子序列是多少if (nums[j] < nums[i]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = max > dp[i] ? max : dp[i];}return max;}
}

全排列I

class Solution {List<List<Integer>> res = new ArrayList(); // 所有結果集List<Integer> list = new ArrayList(); // 當前結果集public List<List<Integer>> permute(int[] nums) {boolean[] used = new boolean[nums.length]; // 判斷當前元素是否加入結果集dfs(nums, used);return res;}public void dfs(int[] nums, boolean[] used) {if (list.size() == nums.length) { // 當前結果集長度等于數組長度即可加入所有結果集res.add(new ArrayList(list));}for (int i = 0; i < nums.length; i++) {if (used[i] == false) { // 判斷元素是否加入當前結果集list.add(nums[i]); // 元素入集合used[i] = true; // 設置元素狀態為被使用dfs(nums, used);used[i] = false; // 回溯list.remove(list.size() - 1);}}}
}

?全排列II

class Solution {List<List<Integer>> res = new ArrayList(); // 所有結果集合List<Integer> list = new ArrayList(); // 當前結果集合Set<List<Integer>> set = new HashSet(); // 結果集去重public List<List<Integer>> permuteUnique(int[] nums) {boolean[] flag = new boolean[nums.length]; // 判斷元素是否加入當前結果集dfs(nums, flag);return res;}public void dfs(int[] nums, boolean[] flag) {if (list.size() == nums.length) { // 當前結果集合等于數組長度即可加入最終結果集List<Integer> tem = new ArrayList(list);if (!set.contains(tem)) { // 判斷該結果集是否在最終結果集中存在set.add(tem); // 該結果集的順序存入去重集合中，避免重復加入最終結果集res.add(tem);}}for (int i = 0; i < nums.length; i++) {if (flag[i] == false) {list.add(nums[i]);flag[i] = true;dfs(nums, flag);flag[i] = false;list.remove(list.size() - 1);}}}
}

?N皇后

class Solution {List<List<String>> res = new ArrayList(); // 最終結果集合List<String> list = new ArrayList(); // public List<List<String>> solveNQueens(int n) {char[][] board = new char[n][n]; // 創建棋盤并初始化for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {board[i][j] = '.';}}dfs(board, n, 0);return res;}public void dfs(char[][] board, int n, int row) {if (row == n) { // 當第row行也可以放棋子說明該方法合法res.add(printResult(board, n));return;}for (int col = 0; col < n; col++) {// 判斷該位置是否可以填棋if (isFlag(board, row, col)) {board[row][col] = 'Q';dfs(board, n, row + 1);board[row][col] = '.';}}}// 核心方法判斷棋子放置位置是否合法public boolean isFlag(char[][] board, int row, int col) { // 判斷該位置放棋子是否合法int n = board.length;for (int i = 0; i < n; i++) { // 同一列不能有皇后if (board[i][col] == 'Q') return false;}for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { // 右斜線不能有皇后if (board[i][j] == 'Q') return false;}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { // 左斜線不能有皇后if (board[i][j] == 'Q') return false;}return true; // 合法}public List<String> printResult(char[][] board, int n) { // 按照題目要求打印結果集List<String> list = new ArrayList();for (int i = 0; i < n; i++) {StringBuilder sb = new StringBuilder();for (int j = 0; j < n; j++) {sb.append(board[i][j]);}list.add(sb.toString());}return list;}
}

?解數獨

class Solution {public void solveSudoku(char[][] board) {dfs(board);}public boolean dfs(char[][] board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') {// 填充數字for (char c = '1'; c <= '9'; c++) {if (isFlag(board, i, j, c)) {board[i][j] = c; // 暫時填充該數字if (dfs(board)) return true;board[i][j] = '.'; // 遞歸到后面不合法，回溯}}return false;}}}return true;}// 核心方法，判斷該位置的數字是否合法public boolean isFlag(char[][] board, int row, int col, char c) { // 判斷該數字是否重復for (int i = 0; i < 9; i++) {// 同行出現過if (board[i][col] == c) return false; // 同列出現過if (board[row][i] == c) return false; // 九宮格出現過if (board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == c) return false;}return true;}
}