算法训练营day27

一、组合总和

参考链接39. 组合总和 - 力扣（LeetCode）

前置题46. 全排列 - 力扣（LeetCode）

注意理解 used[i]数组(全排列) 和 begin变量(组合总和)的区别

因为i是由 begin赋值的，那么当这层遍历执行 path.addLast(candidates[i])时选不到小于 begin索引的值

java">import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {int len = candidates.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}Deque<Integer> path = new ArrayDeque<>();dfs(candidates, 0, len, target, path, res);return res;}/*** @param candidates 候选数组* @param begin      搜索起点* @param len        冗余变量，是 candidates 里的属性，可以不传* @param target     每减去一个元素，目标值变小* @param path       从根结点到叶子结点的路径，是一个栈* @param res        结果集列表*/private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {// target 为负数和 0 的时候不再产生新的孩子结点if (target < 0) {return;}if (target == 0) {res.add(new ArrayList<>(path));return;}// 重点理解这里从 begin 开始搜索的语意
// 因为i是由 begin赋值的，那么当这层遍历 执行 path.addLast(candidates[i])时 选不到小于 begin索引 的值for (int i = begin; i < len; i++) {path.addLast(candidates[i]);// 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错dfs(candidates, i, len, target - candidates[i], path, res);// 状态重置path.removeLast();}}
}

什么时候使用 used 数组，什么时候使用 begin 变量？

排列问题，讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为不同列表时），需要记录哪些数字已经使用过，此时用 used 数组；
组合问题，不讲究顺序（即 [2, 2, 3] 与 [2, 3, 2] 视为相同列表时），需要按照某种顺序搜索，此时使用 begin 变量。
注意：具体问题应该具体分析，理解算法的设计思想是至关重要的，请不要死记硬背。

二、组合总和2

参考链接40. 组合总和 II - 力扣（LeetCode）

java">import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;public class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {int len = candidates.length;List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}// 关键步骤Arrays.sort(candidates);Deque<Integer> path = new ArrayDeque<>(len);dfs(candidates, len, 0, target, path, res);return res;}/*** @param candidates 候选数组* @param len        冗余变量* @param begin      从候选数组的 begin 位置开始搜索* @param target     表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件* @param path       从根结点到叶子结点的路径* @param res*/private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {if (target == 0) {res.add(new ArrayList<>(path));return;}for (int i = begin; i < len; i++) {// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 breakif (target - candidates[i] < 0) {break;}// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continueif (i > begin && candidates[i] == candidates[i - 1]) {continue;}path.addLast(candidates[i]);// 调试语句 ①// System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));// 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 idfs(candidates, len, i + 1, target - candidates[i], path, res);path.removeLast();// 调试语句 ②// System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));}}public static void main(String[] args) {int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};int target = 8;Solution solution = new Solution();List<List<Integer>> res = solution.combinationSum2(candidates, target);System.out.println("输出 => " + res);}
}