1.组合总和问题
原题：力扣39.
元素可以重复拿取，且题目的测试用例保证了组合数少于 150 个。
class CombinationSum {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(candidates, 0, target);
return res;
}
// u 是开始遍历的索引
public void dfs(int[] c, int u, int target) {
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList(path));
return;
}
// 由于元素可以重复，所以 i 从传入的 i 开始继续遍历
for (int i = u; i < c.length; i++) {
if (c[i] <= target) {
path.add(c[i]);
dfs(c, i, target - c[i]);
path.remove(path.size() - 1);
}
}
}
}
2.分割回文串
原题：力扣131.
先取第一个数与后边分开，再取前两个数与后边分开，以此类推…
class Pritition {
List<List<String>> lists = new ArrayList<>();
Deque<String> deque = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return lists;
}
// 回溯算法
private void backTracking(String s, int startIndex) {
// 已经遍历完成，可以作为一组方案添加到 lists 里面
if (startIndex >= s.length()) {
lists.add(new ArrayList(deque));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
deque.addLast(str);
} else {
continue;
}
backTracking(s, i + 1);
deque.removeLast();
}
}
// 判断回文串
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
}
3.子集问题
原题：力扣78.
子集问题往往是要取得所有结果，所以不需要找到满足条件的结果或者剪枝。
class Subsets {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> subsets(int[] nums) {
// 空集合
if (nums.length == 0) {
result.add(new ArrayList<>());
return result;
}
subsetsHelper(nums, 0);
return result;
}
private void subsetsHelper(int[] nums, int startIndex) {
// 之前的可以作为一个子集
result.add(new ArrayList<>(path));
if (startIndex >= nums.length) {
return;
}
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
subsetsHelper(nums, i + 1);
path.removeLast();
}
}
}
4.排列问题
原题：力扣46.
class Permute {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return result;
}
used = new boolean[nums.length];
permuteHelper(nums);
return result;
}
private void permuteHelper(int [] nums) {
// 排列完了，加入结果
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
permuteHelper(nums);
path.removeLast();
used[i] = false;
}
}
}
5.字母大小写全排列
原题：力扣784.
数字是干扰项，排除就好。字母的大小写转换用异或 32 来操作。
class LetterCasePermutation {
public List<String> letterCasePermutation(String s) {
List<String> ans = new ArrayList<String>();
dfs(s.toCharArray(), 0, ans);
return ans;
}
public void dfs(char[] arr, int pos, List<String> res) {
while (pos < arr.length && Character.isDigit(arr[pos])) {
pos++;
}
if (pos == arr.length) {
res.add(new String(arr));
return;
}
arr[pos] ^= 32;
dfs(arr, pos + 1, res);
arr[pos] ^= 32;
dfs(arr, pos + 1, res);
}
}
6.单词搜索
原题：力扣79.
class Exist {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
// 这里不要简写
if (dfs(board, words, i, j, 0)) {
return true;
}
}
}
return false;
}
// k 代表了 word 取到了第几个字符
boolean dfs(char[][] board, char[] words, int i, int j, int k) {
if (i >= board.length || i < 0 || j >= board[0].length || j < 0 || board[i][j] != words[k]) {
return false;
}
// 终止条件
if (k == words.length - 1) {
return true;
}
// 改成终止符，不允许再次访问
board[i][j] = '\0';
boolean res = dfs(board, words, i + 1, j, k + 1) ||
dfs(board, words, i - 1, j, k + 1) ||
dfs(board, words, i, j + 1, k + 1) ||
dfs(board, words, i, j - 1, k + 1);
// 使用后再改回来，即前面题目的 remove 操作
board[i][j] = words[k];
return res;
}
}
如果对您有帮助，请点赞关注支持我，谢谢！
如有错误或者不足之处，敬请指正！
个人主页：星不易
算法通关村专栏：不易|算法通关村
