经典的回溯算法题leetcode组合问题整理及思路代码详解
目录
组合问题
leetcode77题.组合
leetcode216题.组合总和III
leetcode40题.组合总和II
leetcode39题.组合总和
倘若各位不太清楚回溯算法可以去看我上一篇文章。
回溯算法详解-CSDN博客
组合问题
一般组合和排列类的问题我们都会转化成一个树形问题，更便于理解。
leetcode77题.组合
77. 组合 - 力扣（LeetCode）
题目：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
class Solution {
// 创建存放结果集
List<List<Integer>> res = new ArrayList<>();
// 存放单个子集
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {
backTrace(n, k , 1);//index从1开始选，之后选2、选3
return res;
}
//一般回溯操作没有返回值，index表示我们选到了哪里，比如我们选到了1、2、3
void backTrace(int n, int k, int index){
// 优化：称之为剪枝，看能否有k个元素可以选
//选进去的元素 + 可选元素 < k
if(temp.size() + (n - index + 1) < k){
return;
}
// 结束条件：我们已经选了k个元素
if(temp.size() == k){
res.add(new ArrayList<>(temp));
return;
}
// 从多个元素中逐一选择，从index到n就是我们的可选子集
for(int i = index; i <= n; i++){
// 选元素进行处理，比如选了1
temp.add(i);
// 继续下一层，即2、3、4
backTrace(n, k, i + 1);
// 撤销我们处理过的元素
temp.remove(temp.size() - 1);
}
}
}
leetcode216题.组合总和III
216. 组合总和 III - 力扣（LeetCode）
找出所有相加之和为
n的k个数的组合，且满足下列条件：
- 只使用数字1到9
- 每个数字最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
class Solution {
//保存最终的结果
List<List<Integer>> res = new ArrayList<>();
//临时的保存每一组成立的结果
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
backTrace(n, k, 1, 0);
return res;
}
void backTrace(int n, int k, int index, int sum){
// 优化剪枝
if(sum > n){
return;
}
//凑不到k个数-> 可选的数 + 已选的数 < k
if((9 - index + 1) + temp.size() < k){
return;
}
// 结束条件：已经选了k个数
if(temp.size() == k){
if(sum == n){
res.add(new ArrayList<>(temp));
}
return;
}
// 回溯
for(int i = index; i <= 9; i++){
// 选其中一个元素
temp.add(i);
sum = sum + i;
backTrace(n, k, i + 1, sum);
// 撤销处理
temp.remove(temp.size() - 1);
sum = sum - i;
}
}
}
leetcode40题.组合总和II
40. 组合总和 II - 力扣（LeetCode）
给定一个候选人编号的集合
candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次 。注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
class Solution {
//存结果的结果集
List<List<Integer>> res = new ArrayList<>();
//临时变量存子集
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);//给数组排序
backTrack(candidates, target, 0, 0);//index表示数组下标，从0开始
return res;
}
/*
怎么处理重复的组合
1. 排序 [1, 1, 5, 6, 7, 10];
*/
void backTrack(int[] candidates, int target, int index, int sum){
//剪枝
if(sum > target){
return;
}
// 结束条件
if(sum == target){
res.add(new ArrayList<>(temp));
return;
}
// 处理主要逻辑
for(int i = index; i < candidates.length; i++){
// 遇到重复的数就跳过，去掉重复的组合
if(i > index && candidates[i] == candidates[i-1]){
continue;
}
// 从多个元素选择一个
temp.add(candidates[i]);
sum = sum + candidates[i];
backTrack(candidates, target, i + 1, sum);
// 撤销之前的操作
temp.remove(temp.size() - 1);
sum = sum - candidates[i];
}
}
}
leetcode39题.组合总和
39. 组合总和 - 力扣（LeetCode）
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
class Solution {
//存取结果
List<List<Integer>> res = new ArrayList<>();
//临时存取子集
List<Integer> temp = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backTrack(candidates, target, 0, 0);
return res;
}
void backTrack(int[] candidates, int target, 0int index, int sum){
// 剪枝
if(sum > target){
return;
}
// 结束条件
if(sum == target){
res.add(new ArrayList<>(temp));
return;
}
// 处理主要逻辑
for(int i = index; i < candidates.length; i++){
// 从多个元素选择一个
temp.add(candidates[i]);
sum = sum + candidates[i];
//可以重复选择i，所以不用i+1
backTrack(candidates, target, i, sum);
// 撤销之前的操作
temp.remove(temp.size() - 1);
sum = sum - candidates[i];
}
}
}