题解 | #牛群喂食#

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