1 组合问题
LeeCode 39：组合总和
题目描述
给你一个 无重复元素 的整数数组
candidates和一个目标整数target，找出candidates中可以使数字和为目标数target的所有 不同组合，并以列表形式返回。
candidates中的同一个数字可以 无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
\(1 \le candidates.length \le 30\)
\(1 \le candiates[i] \le 200\)
\(1 \le target \le 500\)
建立模型
- 关键要求：数字可以重复选取
定义递归函数
combinationSumImpl(int[] candidates, int index, int sum, int target)确定递归终止条件
sum == target剪枝优化，当
sum > target 时，无需再往下一层递归，可以直接 return代码实现
public class Solution {
/**
* 定义两个全局变量
* @param res: 存储所有符合条件的组合
* @param temp: 存储当前组合包含的数
*/
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
combinationSumImpl(candidates, 0, 0, target);
return res;
}
public void List<Integer> combinationSumImpl(int[] candidates, int index, int sum, int target) {
/**
* 递归终止条件
*/
if (sum == target) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = index; i < candidates.length; i++) {
// 剪枝: 若加上当前元素已经超过目标值，则无需继续递归下一层
// 因为 candidates 是递增排序的，再添加后面的值肯定也会超过目标值
if (sum + candidates[i] > target) {
break;
}
temp.add(candidates[i]);
/**
* 允许重复选取元素
* 所以下一层递归从当前元素开始
*/
combinationSumImpl(candidates, i, sum + candidates[i], target);
temp.remove(temp.size() - 1);
}
}
}
LeeCode 40：组合总和II
题目描述
给的一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中每个数字在每个组合中只能使用一次。解集不能包含重复的组合。
\(1 \le candidates.length \le 100\)
\(1 \le candidates[i] \le 50\)
\(1 \le target \le 30\)
建立模型
- 本题与
LeeCode 39：组合总和 最主要的区别就是：每个数字只能使用一次，但 candidates 中数字是可以重复的定义递归函数
combinationSum2Impl(int[] candidates, int index, int sum, int target)确定递归终止条件：
sum == target去除重复项，因为
candidates 中存在重复数字，导致回溯过程中会产生重复的组合剪枝优化，当
sum > target 时，无需再往下一层递归，可以直接 return代码实现
public class Solution {
/**
* 定义两个全局变量
* @param res: 存储所有符合条件的组合
* @param temp: 存储当前组合包含的数
*/
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
}
public void combinationSum2Impl(int[] candidates, int index, int sum, int target) {
if (sum == target) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = index; i < candidates.length; i++) {
/**
* 去除重复项目
* i > index: 说明没有选择前一个数字
* 若此时当前数字等于前一个数字，则递归当前数字的所有组合均在递归前一个数字时出现过
* 所以跳过当前数字的递归
*/
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}
// 剪枝: 若加上当前元素已经超过目标值，则无需继续递归下一层
// 因为 candidates 是递增排序的，再添加后面的值肯定也会超过目标值
if (sum + candidates[i] > target) {
break;
}
temp.add(candidates[i]);
/**
* 每个数字只能选取一次，所以下一层递归从当前数字后面一个开始
*/
combinationSum2Impl(candidates, i + 1, sum + candidates[i], target);
temp.remove(temp.size() - 1);
}
}
}
LeeCode 216：组合总和III
题目描述
找出所有相加之和为
n的k个数的组合，且满足下列条件：只能使用数字 1~9
每个数字最多使用一次返回所有可能的有效组合的列表。解集不能包含重复的组合。
建立模型
- 本题与
LeeCode 40 组合总和II 主要的区别是：目标不仅有值约束(n)还有个数约束(k)，但 candidates 是固定的 [1, 2, 3, 4, 5, 6, 7, 8, 9]定义递归函数
combinationSum3Impl(int k, int n, int sum, int index)确定递归终止条件
temp.size() == k || (temp.size() < k && sum >= n)剪枝优化，当
temp.size() == k && sum >= n 时，无需再往下一层递归，可直接返回剪枝优化，当
index > 9 - (k - temp.size()) + 1 时，即把后面所有项都加上也无法满足 k 项代码实现
public class Solution {
/**
* 定义两个全局变量
* @param res: 存储所有符合条件的组合
* @param temp: 存储当前组合包含的数
*/
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
combinationSum3Impl(k, n, 0, 0);
}
public void combinationSum3Impl(int k, int n, int sum, int index) {
// 递归终止条件1：temp.size() == k
if (temp.size() == k) {
if (sum == n) {
res.add(new ArrayList<>(temp));
}
return;
}
/**
* 递归终止条件2：temp.size() < k && sum >= n
* 剪枝优化
* 当前和已经大于等于目标值，但个数还不满足，又只能添加正数，所以继续添加不可能满足要求
*/
if (sum >= n) {
return;
}
/**
* 剪枝优化
* 若 i > 9 - (k - temp.size()) + 1
* 则把当前项后面所有项都加上，无法满足 k 项，所有不可能满足要求
*/
for (int i = index; i <= 9 - (k - temp.size()) + 1; i++) {
temp.add(i);
combinationSum3Impl(k, n, sum + i, i + 1);
temp.remove(temp.size() - 1);
}
}
}
2 子集问题
LeeCode 78：子集
题目描述
给你一个整数数组
nums，数组中的元素互不相同。返回该数组所有可能的子集。解集不能包含重复的子集。可以按任意顺序返回子集。
建立模型
- 通过递归来实现子集的枚举
关键信息：数组中的元素互不相同，所有枚举过程中不会出现重复的子集
定义递归函数
subsetsImpl(int[] nums, int index)确定递归终止条件
index == nums.length代码实现
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsets(int[] nums) {
subsetsImpl(nums, 0);
return res;
}
public void subsetsImpl(int[] nums, int index) {
if (index == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
// 添加当前元素递归
temp.add(nums[index]);
subsetsImpl(nums, index + 1);
// 不添加当前元素递归
temp.remove(temp.size() - 1);
subsetsImpl(nums, index + 1);
}
}
LeeCode 90：子集II
题目描述
给你一个整数数组
nums，其中可能包含重复元素，请你返回该数组所有可能的子集。解集不能包含重复的子集。返回的解集中，子集可以按任意顺序排列。
建立模型
- 本题与
LeeCode 78 子集 最主要的区别就是：nums 中存在重复元素，枚举子集的过程中会产生重复的子集关键信息：
nums 中存在重复元素，枚举子集过程中如何去重定义递归函数
subsetsWithDupImpl(int[] nums, int index, boolean flag)确定递归终止条件
index == nums.length去除重复子集条件
!flag && index > 0 && nums[index] == nums[index - 1]代码实现
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
subsetsWithDupImpl(nums, 0, false);
return res;
}
/**
* @param flag: 表示是否 temp 中是否包含当前元素的前一个元素
*/
public void subsetsWithDupImpl(int[] nums, int index, boolean flag) {
if (index == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
subsetsWithDupImpl(nums, index + 1, false); // 不添加当前元素
/**
* flag = false: 未添加前一个元素
* index > 0: 不是首元素
* nums[index] == nums[index - 1]: 当前元素 等于 前一个元素
*
* 此时递归当前元素产生的子集均在递归前一个元素时出现过
* 所以跳过当前数字的递归
*/
if (!flag && index > 0 && nums[index] == nums[index - 1]) {
return;
}
temp.add(nums[index]);
subsetsWithDupImpl(nums, index + 1, true); // 添加当前元素
temp.remove(temp.size() - 1);
}
}
3 排列问题
LeeCode 46：全排列
题目描述
给定一个不含重复数字的数组
nums，返回其所有可能的全排列。你可以按任意顺序返回答案。
\(1 \le nums.length \le 6\)
\(-10 \le nums[i] \le 10\)
nums 所有数互不相同
建立模型
- 相较于组合问题，排列问题中的数字有顺序
关键信息：
nums 不包含重复元素，所有递归过程中不会产生重复的排列定义
used 数组，标识元素是否已经使用过定义递归函数
permuteImpl(int[] nums, int index, boolean[] used)确定递归终止条件
index == nums.length代码实现
// 实现方式一
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
permuteImpl(nums, 0, used);
return res;
}
public void permuteImpl(int[] nums, int index, boolean[] used) {
if (index == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
// 对于第 index 位，尝试填入 nums 中的每一个数字
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
used[i] = true;
temp.add(nums[i]);
permuteImpl(nums, index + 1, used);
temp.remove(temp.size() - 1);
used[i] = false;
}
}
}
}
// 实现方式二, 不使用标记数组
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
for (int num : nums) {
temp.add(num);
}
permuteImpl(nums, 0);
return res;
}
public void permuteImpl(int[] nums, int index) {
if (index == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
/**
* 0 ~ index - 1: 已填充位置
* index ~ nums.length - 1: 待填充位置
*
* 使用 [index, nums.length - 1]里的数去填充第 index 个数
* 即 Collections.swap(temp, index, i)
*/
for (int i = index; i < nums.length; i++) {
Collections.swap(temp, index, i);
permuteImpl(nums, index + 1);
Collections.swap(temp, index, i);
}
}
}
LeeCode 47 全排列II
题目描述
给定一个包含重复数字的序列
nums，按任意顺序返回所有不重复的全排列。
\(1 \le nums.length \le 8\)
\(-10 \le nums[i] \le 10\)
建立模型
- 本题与
LeeCode 46 全排列 最大的区别就是：nums 中存在重复元素，递归过程中会产生重复的排列定义递归函数
permuteUniqueImpl(int[] nums, int index, boolean[] used)确定递归终止条件
index == nums.length去除重复排列条件
(i > 0 && nums[i] == nums[i - 1] && !used[i - 1])代码实现
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums); // 排序使得相同的数字出现在一起
boolean[] used = new boolean[nums.length];
}
public void permuteUniqueImpl(int[] nums, int index, boolean[] used) {
if (index == nums.length) {
res.add(new ArrayList<>(temp));
return;
}
for (int i = 0; i < nums.length; i++) {
/**
* 去重重复排列
* i > 0: 当前元素不是首元素
* nums[i] == nums[i - 1]: 当前元素等于前一个元素
* !used[i - 1]: 未添加前一个元素
*
* 即在当前 index 位置添加当前元素产生的排列，均在 当前index位置添加前一个元素中 出现过
* 所以跳过此元素
*/
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
continue;
}
temp.add(nums[i]);
used[i] = true;
permuteUniqueImpl(nums, index + 1, used);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
4 其它回溯问题
LeeCode 491：递增子序列
题目描述
给你一个整数数组
nums，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
建立模型
关键信息：nums 中存在重复元素，所以可能会产生重复的子序列
定义递归函数 findSubsequenceImpl(int[] nums, int index, int lastValue)
确定递归终止条件 index == nums.length
去除重复子序列条件 nums[index] != lastValue ，如果有两个连续元素相同，会产生四种情况：
- 前者被添加，后者也被添加
前者不被添加，后者也不被添加
前者被添加，后者不被添加
前者不被添加，后者被添加
情况3和情况4是等价的，即会产生重复子序列，所以通过 nums[index] != lastValue 条件去除情况3，保留情况4。
代码实现
public class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> findSubsequence(int[] nums) {
findSubsequenceImpl(nums, 0, Integer.MIN_VALUE);
return res;
}
/**
* @param lastValue: temp最近添加的元素值
*/
public void findSubsequenceImpl(int[] nums, int index, int lastValue) {
if (index == nums.length) {
if (temp.size() >= 2) {
res.add(new ArrayList<>(temp));
}
return;
}
// 添加当前元素递归
if (nums[index] >= lastValue) {
temp.add(nums[index]);
findSubsequenceImpl(nums, index + 1, nums[index]);
temp.remove(temp.size() - 1);
}
// 若当前值不等于最近添加的值，则不添加当前元素递归
if (nums[index] != lastValue) {
findSubsequenceImpl(nums, index + 1, lastValue);
}
// 若当前值等于最近添加的值，则不进行递归返回
return;
}
}
LeeCode 131：分割回文串
题目描述
给你一个字符串
s，请你将s分割成一些子串，使每个子串都是回文串。返回s所有可能的分割方案。
建立模型
- 本题本质上是一个组合问题，且不会产生重复的解集
关键问题：判断回文串
构建记忆化搜索函数辅助判断回文串
isPalindrome(String s, int i, int j, int[][] dp)定义递归函数
partitionImpl(String s, int index, int[][] dp)确定递归终止条件
index == s.length()代码实现
public class Solution {
List<List<String>> res = new ArrayList<>();
List<String> temp = new ArrayList<>();
public List<List<String>> partition(String s) {
int[][] dp = new int[s.length()][s.length()];
partitionImpl(s, 0, dp);
return res;
}
public void partitionImpl(String s, int index, int[][] dp) {
if (index == s.length()) {
res.add(new ArrayList<>(temp));
return;
}
/**
* 尝试 [index, s.length() - 1] 中所有的回文串，并递归
*/
for (int i = index; i < s.length(); i++) {
if (isPalindrome(s, index, i, dp) == 1) {
temp.add(s.substring(index, i + 1));
partitionImpl(s, i + 1, dp);
temp.remove(temp.size() - 1);
}
}
}
/**
* @param i: 起始位置
* @param j: 结束位置
* @return 1: 是回文串
* @return -1: 不是回文串
*/
public int isPalindrome(String s, int i, int j, int[][] dp) {
if (dp[i][j] != 0) {
return dp[i][j];
}
if (i >= j) {
dp[i][j] = 1;
}
else if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i + 1][j - 1];
}
else {
dp[i][j] = -1;
}
return dp[i][j];
}
}
