39(40、216)-组合总和Ⅰ、Ⅱ、Ⅲ-典型回溯问题
2020-03-21 本文已影响0人
华雨欣
题目
分析
回溯问题最简单的思想就是直接dfs暴力搜索,找出每一种情况即可,不过这样的时间效率不会很高,需要进一步的优化(剪枝)。另外,题目需要得到和为 target 的组合的集合,由于给定数组没有重复元素,故只要保证 下一次搜索的数的下标 >= 当前下标 即可避免出现重复解集。我们可以采用减法使得每次遍历到一个数就将 target 值减去遍历元素传递给更深一层,target <= 0 时递归结束返回(当然加法也同理,用一个变量记录和,和等于 target 时递归结束返回)。分析图如下:可以得到代码如下:
class Solution {
List<List<Integer>> ans = new ArrayList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
dfs(candidates, target, 0, new Stack<Integer>());
return ans;
}
public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
if (target == 0) {
ans.add(new ArrayList<Integer>(com));
} else if (target > 0) {
for (int i = index; i < candidates.length; i++) {
com.push(candidates[i]);
dfs(candidates, target - candidates[i], i, com);
com.pop();
}
}
}
}
成功AC,不过时间方面还可以再优化。
优化
通过观察分析图,可以发现,对于排好序的数组,只要小的数不满足条件,后边的元素遍都可以不用遍历了,从而可以实现剪枝,代码如下:
class Solution {
List<List<Integer>> ans = new ArrayList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
//排序方便剪枝
Arrays.sort(candidates);
dfs(candidates, target, 0, new Stack<Integer>());
return ans;
}
public void dfs(int[] candidates, int target, int index, Stack<Integer> com) {
if (target == 0) {
ans.add(new ArrayList<Integer>(com));
} else if (target > 0) {
for (int i = index; i < candidates.length; i++) {
//数组元素比当前目标大,后边的元素都不用遍历了
if (target < candidates[i])
break;
com.push(candidates[i]);
dfs(candidates, target - candidates[i], i, com);
com.pop();
}
}
}
}
提交后大概3ms,比较令人满意的效率。
组合总和Ⅱ
题目如下:
分析
与第一题相比,数组包含重复元素,但是每个数字只能使用一次,这就说明,在第一题基础上,当向深层遍历的时候只能从当前的元素向后遍历(不含当前元素)。但是有重复元素,哪怕排完序也会出现重复的解集组合,不过对于下面数组示例可以发现:排序后的数组对于重复的数字会出现重复的解,但是第一个元素(第一个1、3)不会出现重复,所以,从第一个之后跳过所有重复的数字即可,即:
/* 跳过重复的数字 */
if (i > index && candidates[i] == candidates[i - 1])
continue;
完整代码
class Solution {
ArrayList<List<Integer>> ans = new ArrayList();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
dfs(candidates, target, new Stack<Integer>(), 0);
return ans;
}
public void dfs(int[] candidates, int target, Stack<Integer> stack, int index) {
if (target < 0) {
return;
} else if (target == 0) {
ans.add(new ArrayList<Integer>(stack));
} else {
for (int i = index; i < candidates.length; i++) {
if (candidates[i] > target) {
break;
}
if (i > index && candidates[i] == candidates[i - 1])
continue;
stack.add(candidates[i]);
dfs(candidates, target - candidates[i], stack, i + 1);
stack.pop();
}
}
}
}
整体思路与第一题没什么差别,主要是一点细节上的处理。
组合总和Ⅲ
题目如下:第三题思路与前两题基本一致,甚至难度比前两题还要小一点,就不再讲解,给出完整代码:
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
ArrayList<List<Integer>> ans = new ArrayList();
dfs(k, n, ans, new Stack<Integer>(), 1);
return ans;
}
public void dfs(int k, int n, ArrayList<List<Integer>> ans, Stack<Integer> stack, int start){
if(k == 0){
if(n == 0){
ans.add(new ArrayList(stack));
}
}else{
for(int i = start; i <= 9; i++){
stack.push(i);
if(i > n){
stack.pop();
break;
}
dfs(k - 1, n - i, ans, stack, i + 1);
stack.pop();
}
}
}
}
认真总结,仔细研究,未来可期。