题解 | #牛群喂食# java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    public int[][] cowCombinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> combination = new ArrayList<>();
        dfs(candidates, target, result, combination, 0);

        int[][] ans = new int[result.size()][];
        for (int i = 0; i < result.size(); i++) {
            List<Integer> list = result.get(i);
            ans[i] = new int[list.size()];
            for (int j = 0; j < list.size(); j++) {
                ans[i][j] = list.get(j);
            }
        }

        return ans;
    }

    public void dfs(int[] candidates, int target, List<List<Integer>> result,
                    List<Integer> combination, int begin) {
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }
        for (int i = begin; i < candidates.length && target >= candidates[i]; i++) {
            combination.add(candidates[i]);
            dfs(candidates, target - candidates[i], result, combination, i);
            combination.remove(combination.size() - 1);
        }
    }
}

使用的是Java语言。

该题考察的知识点是回溯算法和数组操作。回溯算法用于生成给定数组中元素的所有组合和满足条件的组合。代码中通过递归的方式实现回溯过程，根据当前选择的元素，将其添加到组合中或继续递归调用，直到生成满足条件的组合。

代码的文字解释如下：

• 在cowCombinationSum方法中，对给定的整型数组进行排序，并初始化结果集result和成员变量combination。
• 调用dfs方法开始回溯过程，初始索引为0，初始空列表。
• dfs方法是核心的递归函数。在每一轮回溯中，从给定数组的开始位置开始遍历，如果当前元素小于等于目标值，则将其添加到组合中。然后继续递归调用dfs方法，传递更新后的目标值和增加了一个元素的组合，以及当前元素的索引。当目标值等于0时，表示已生成一个满足条件的组合，将其添加到结果集中。回溯过程中，需要注意在递归结束后将最后一个添加的元素移除，以便尝试其他可能的组合。
• 在回溯完成后，根据结果集的大小创建二维数组ans，并将结果集中的组合转移到ans中。
• 返回二维数组ans作为最终结果。