- 排列用visited数组，每次从[0, len）
- 组合用start控制重复
- 子集问题和组合问题类似，去重方式类似，只不过添加结果的时机不一致
77. 组合
// 注意start的含义，以及剪枝处理
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private int n;
private int k;
private List<Integer> trace = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
this.n = n;
this.k = k;
dfs(1);
return res;
}
private void dfs(int start) {
if (trace.size() == k) {
res.add(new ArrayList<>(trace));
return;
}
for (int i = start; i <= n - (k - trace.size()) + 1; i++) {
trace.add(i);
dfs(i+1);
trace.remove(trace.size() - 1);
}
}
}
39. 组合总和
// 注意可以去重复的处理，以及求和的处理
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private int target;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
this.target = target;
dfs(candidates, 0, 0);
return res;
}
private void dfs(int[] nums, int sum, int start) {
if (sum > target) return;
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.length; i++) { // 不能从0开始
path.add(nums[i]);
sum += nums[i];
dfs(nums, sum, i);
path.remove(path.size()-1);
sum -= nums[i];
}
}
}
40. 组合总和 II
// 排序后用set也可以去重，但是会超时，最后几个用例通不过
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private int target;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
this.target = target;
Arrays.sort(candidates);
dfs(0, 0, candidates);
return res;
}
private void dfs(int start, int sum, int[] nums) {
if (sum > target) {
return;
}
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) continue; // 此题去重的精髓所在
path.add(nums[i]);
sum += nums[i];
dfs(i + 1, sum, nums);
path.remove(path.size() - 1);
sum -= nums[i];
}
}
}
216. 组合总和 III
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> res = new ArrayList<>();
private int k;
private int n;
public List<List<Integer>> combinationSum3(int k, int n) {
this.k = k;
this.n = n;
dfs(1, 0);
return res;
}
private void dfs(int start, int sum) {
if (path.size() > k || sum > n) {
return;
}
if (path.size() == k && sum == n) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i <= 9 - (k - path.size()) + 1; i++) {
path.add(i);
sum += i;
dfs(i+1, sum);
path.remove(path.size()-1);
sum -= i;
}
}
}
46. 全排列
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private boolean[] flag = new boolean[7];
public List<List<Integer>> permute(int[] nums) {
dfs(nums);
return res;
}
private void dfs(int[] nums) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
}
for (int i = 0; i < nums.length; i++) { // 每次都是从0开始，在path中的打标记
if (flag[i]) continue;
path.add(nums[i]);
flag[i] = true;
dfs(nums);
path.remove(path.size()-1);
flag[i] = false;
}
}
}
47. 全排列 II
// 用set去重也可以，能通过，但是效率较低
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] flag = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, flag);
return res;
}
private void dfs(int[] nums, boolean[] flag) {
if (path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (flag[i]) continue;
if (i > 0 && nums[i-1] == nums[i] && !flag[i-1]) continue; // 注意这里的判断，相比组合多了一个flag判断
path.add(nums[i]);
flag[i] = true;
dfs(nums, flag);
path.remove(path.size()-1);
flag[i] = false;
}
}
}
784. 字母大小写全排列，*
// 每个dfs函数完成一定的任务，不一定都有for循环
class Solution {
private List<String> res = new ArrayList<>();
public List<String> letterCasePermutation(String s) {
char[] chs = s.toCharArray();
bfs(chs, 0);
return res;
}
private void dfs(char[] chs, int pos) {
if (pos == chs.length) {
res.add(new String(chs));
return;
}
if (Character.isDigit(chs[pos])) {
dfs(chs, pos+1);
return;
}
chs[pos] = Character.toLowerCase(chs[pos]);
dfs(chs, pos+1);
chs[pos] = Character.toUpperCase(chs[pos]);
dfs(chs, pos+1);
}
}
78. 子集
// 和组合问题一样，要有个start，注意start的含义
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
dfs(nums, 0);
return res;
}
private void dfs(int[] nums, int start) {
res.add(new ArrayList<>(path)); // 注意要在return之前加入集合
if (start == nums.length) return;
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
dfs(nums, i+1);
path.remove(path.size()-1);
}
}
}
90. 子集 II
// 注意排序+去重的方式
class Solution {
private List<List<Integer>> res = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
dfs(nums, 0);
return res;
}
private void dfs(int[] nums, int start) {
res.add(new ArrayList<>(path));
if (start == nums.length) return;
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i-1]) continue; // 和组合问题的去重一致
path.add(nums[i]);
dfs(nums, i+1);
path.remove(path.size()-1);
}
}
}
17. 电话号码的字母组合
// 典型回溯法，排列问题
class Solution {
private String[] mapArr = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
private List<String> res = new ArrayList<>();
private StringBuilder path = new StringBuilder();
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) return res;
dfs(digits.toCharArray(), 0);
return res;
}
private void dfs(char[] digits, int pos) {
if (pos == digits.length) {
res.add(path.toString());
return;
}
String curStr = mapArr[digits[pos] - '0'];
for (char curChar : curStr.toCharArray()) {
path.append(curChar);
dfs(digits, pos+1);
path.deleteCharAt(path.length()-1);
}
}
}
93. 复原 IP 地址，*
// 还可以用三重循环去搜索这个问题
class Solution {
List<String> res = new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if (s.length() > 12) return res;
backtrace(new StringBuilder(), s, 0, 0);
return res;
}
public void backtrace(StringBuilder path, String s, int start, int index) {
if (index == 4) {
if (path.length() - 3 == s.length()) res.add(path.toString());
return;
}
for (int i = 1; i <= 3 && i <= s.length() - start; i++) {
String sub = s.substring(start, start + i);
if (!valid(sub)) {
continue;
}
if (path.length() != 0) {
sub = "." + sub;
}
path.append(sub);
backtrace(path, s, start + i, index + 1);
path.delete(path.length() - sub.length(), path.length()); // 值得注意
}
}
public boolean valid(String s) {
if (s.length() > 1 && s.charAt(0) == '0') return false;
if (Integer.valueOf(s) > 255) return false;
return true;
}
}
131. 分割回文串
// 搜索算法，搜索到终止条件即满足题意
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> partition(String s) {
backtrace(s, 0, new ArrayList<String>());
return res;
}
public void backtrace(String s, int start, ArrayList<String> path) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 1; i <= s.length() - start; i++) {
String subStr = s.substring(start, start+i);
if (!valid(subStr)) {
continue;
}
path.add(subStr);
backtrace(s, start+i, path);
path.remove(path.size()-1);
}
}
public boolean valid(String s) {
if (s.length() == 0) return false;
int begin = 0;
int end = s.length() - 1;
while (begin < end) {
if (s.charAt(begin) != s.charAt(end)) {
return false;
}
begin++;
end--;
}
return true;
}
}
51. N 皇后
// 按步骤来其实不难，怎么校验是关键
class Solution {
List<List<String>> res = 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, 0);
return res;
}
private void dfs(char[][] board, int colIndex) {
if (colIndex == board.length) {
res.add(constructStr(board));
return;
}
for (int i = 0; i < board.length; i++) {
if (isValid(board, i, colIndex)) {
board[i][colIndex] = 'Q';
dfs(board, colIndex + 1);
board[i][colIndex] = '.';
}
}
}
// 怎么校验是关键
private boolean isValid(char[][] board, int x, int y) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < y; j++) {
if (board[i][j] == 'Q' && (x == i || x + j == y + i || x + y == i + j))
return false;
}
}
return true;
}
private List<String> constructStr(char[][] board) {
List<String> str = new ArrayList<>();
for (int i = 0; i < board.length; i++) {
str.add(new String(board[i]));
}
return str;
}
}
22. 括号生成
// 自己想的，超过100%
class Solution {
private int left;
private int right;
private List<String> res = new ArrayList<>();
private StringBuilder path = new StringBuilder();
public List<String> generateParenthesis(int n) {
this.left = n;
this.right = n;
dfs();
return res;
}
private void dfs() {
if (left > right) return;
if (left == 0) {
int tmp = right;
while (tmp-- > 0) {
path.append(')');
}
res.add(path.toString());
return;
}
int len = path.length();
path.append('(');
left--;
dfs();
path.delete(len, path.length());
left++;
path.append(')');
right--;
dfs();
path.delete(len, path.length());
right++;
}
}
37. 解数独
// 注意递归函数的结构，结束的判断条件，怎么递归，有效值的判断。
class Solution {
public void solveSudoku(char[][] board) {
dfs(board, 0, 0);
}
private boolean dfs(char[][] board, int row, int col) {
if (col == board[0].length) {
col = 0;
row += 1;
}
if (row == board.length) return true;
if (board[row][col] != '.') return dfs(board, row, col + 1);
for (int i = '1'; i <= '9'; i++) {
if (isValid(board, row, col, (char)i)) {
board[row][col] = (char)i;
if (dfs(board, row, col+1)) return true;
board[row][col] = '.';
}
}
return false;
}
private boolean isValid(char[][] board, int row, int col, char value) {
for (int i = 0; i < 9; i++) {
if (board[row][i] != '.' && board[row][i] == value) return false;
if (board[i][col] != '.' && board[i][col] == value) return false;
}
int boxRow = row / 3;
int boxCol = col / 3;
for (int i = boxRow * 3; i < (boxRow+1) * 3; i++) {
for (int j = boxCol * 3; j < (boxCol+1) * 3; j++) {
if (board[i][j] != '.' && board[i][j] == value) return false;
}
}
return true;
}
}
79. 单词搜索
class Solution {
private char[][] board;
private String word;
private int m;
private int n;
public boolean exist(char[][] board, String word) {
this.board = board;
this.word = word;
this.m = board.length;
this.n = board[0].length;
boolean[][] visit = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dfs(i, j, 0, visit)) return true;
}
}
return false;
}
private boolean dfs(int x, int y, int index, boolean[][] visit) {
if (index == word.length()) return true;
if (x < 0 || x >= m || y < 0 || y >= n || visit[x][y]) return false;
if (board[x][y] != word.charAt(index)) return false;
visit[x][y] = true;
if (dfs(x+1, y, index+1, visit) || dfs(x-1, y, index+1, visit) || dfs(x, y+1, index+1, visit) || dfs(x, y-1, index+1, visit))
return true;
visit[x][y] = false;
return false;
}
}
89. 格雷编码
95. 不同的二叉搜索树 II
113. 路径总和 II
126. 单词接龙 II
140. 单词拆分 II
212. 单词搜索 II
254. 因子的组合
class Solution {
public List<List<Integer>> getFactors(int n) {
return dfs(n, 2);
}
private List<List<Integer>> dfs(int n, int start) {
List<List<Integer>> res = new ArrayList<>();
for (int i = start; i * i <= n; i++) {
if (n % i == 0) {
List<Integer> cur = new ArrayList<>();
cur.add(i);
cur.add(n / i);
res.add(cur);
for (List<Integer> list : dfs(n / i, i)) {
list.add(i);
res.add(list);
}
}
}
return res;
}
}
267. 回文排列 II
// 哭了，忍着焦躁的心情AC这题，超过100%。这其实是个全排列问题，排列好前面的n/2个字符，注意排列问题的去重
class Solution {
private List<String> res = new ArrayList<>();
private char[] halfChs;
private char single;
public List<String> generatePalindromes(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c-'a']++;
boolean flag = s.length() % 2 == 0;
char[] chs = new char[s.length() / 2];
char single = ' ';
int k = 0;
for (int i = 0; i < 26; i++) {
if (count[i] % 2 == 1) {
single = (char)(i + 'a');
if (flag) return res;
flag = true;
}
for (int j = 0; j < count[i] / 2; j++) {
chs[k++] = (char)(i + 'a');
}
}
halfChs = chs;
this.single = single;
dfs(new char[s.length()], 0, new boolean[s.length()/2]);
return res;
}
private void dfs(char[] path, int start, boolean[] visit) {
if (start == path.length / 2) {
res.add(conStr(path));
return;
}
for (int i = 0; i < halfChs.length; i++) {
if (visit[i]) continue; // 选过的不选
if (i > 0 && halfChs[i] == halfChs[i-1] && !visit[i-1]) continue; // 前一个没选且等于前一个才continue，注意！！！
path[start] = halfChs[i];
visit[i] = true;
dfs(path, start+1, visit);
visit[i] = false;
}
}
private String conStr(char[] path) {
for (int i = 0; i < path.length / 2; i++) {
path[path.length - i - 1] = path[i];
}
if (path.length % 2 == 1) {
path[path.length / 2] = single;
}
return new String(path);
}
}
