题解 | #牛群喂食#
牛群喂食
https://www.nowcoder.com/practice/591c222d73914c1ba031a660db2ef73f
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param candidates int整型一维数组 * @param target int整型 * @return int整型二维数组 */ private final List<List<Integer>> list = new ArrayList<List<Integer>>(); public int[][] cowCombinationSum (int[] candidates, int target) { dfs(candidates, target, 0, 0, new ArrayList<Integer>()); int length = list.size(); int[][] result = new int[length][]; for (int i = 0; i < length; i++) { List<Integer> l = list.get(i); int[] arr = new int[l.size()]; for (int j = 0; j < l.size(); j++) { arr[j] = l.get(j); } result[i] = arr; } return result; } public void dfs(int[] candidates, int target, int index, int sum, List<Integer> currentList) { if (sum == target) { // 当和等于目标值时,将当前路径添加到全局列表中 list.add(new ArrayList<Integer>(currentList)); return; } // 当前索引超过数组长度或当前和大于目标值 终止条件 if (index >= candidates.length || sum > target) { return; } for (int i = index; i < candidates.length; i++) { if (currentList.size() > 0) { // 判断当前元素是否小于等于前一个元素,如果是,则跳过该元素,避免重复组合 int pre = currentList.get(currentList.size() - 1); if (pre > candidates[i]) { continue; } } // 将当前元素添加到路径中 currentList.add(candidates[i]); sum += candidates[i]; // 递归搜索下一个位置 dfs(candidates, target, index, sum, currentList); // 回溯删除最后一个元素 currentList.remove(currentList.size() - 1); // 回溯还原当前和 sum -= candidates[i]; } } }
知识点:
1.递归+回溯
2.集合转数组
3.数组遍历
4.数学模拟
解题分析:
1. 当和等于目标值时,将当前路径添加到全局列表中
2.当前索引超过数组长度或当前和大于目标值 终止条件
3.判断当前元素是否小于等于前一个元素,如果是,则跳过该元素,避免重复组合(穷举的剪枝操作)
4.将当前元素添加到路径中
5.递归搜索下一个位置
6.回溯删除最后一个元素
7.回溯还原当前和
编程语言:
Java