题解 | #牛群喂食#

知识点：回溯

题目要求找到数组中和为target的序列，并且序列中的元素可以重复，原数组的元素并没有重复元素，这就确保了只有在同一个位置才可以找到该元素，题目还要求需要将最终结果升序排列，我们可以先对原数组进行升序排序，然后依次遍历自身及其后续元素，累加得到的元素和，当元素和等于target时，保存当前遍历的所有元素，当超过target时需要停止后续遍历。

Java题解如下

import java.util.*;


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

    public int[][] cowCombinationSum (int[] candidates, int target) {
        // write code here
        Arrays.sort(candidates);
        this.candidates = candidates;
        this.target = target;
        for(int i = 0; i < candidates.length; i++) {
            dfs(new ArrayList<>(), i, 0);
        }
        int[][] ans = new int[res.size()][];
        for(int i = 0; i < res.size(); i++) {
            ans[i] = new int[res.get(i).size()];
            for(int j = 0; j < res.get(i).size(); j++) {
                ans[i][j] = res.get(i).get(j);
            }
        }
        return ans;
    }

    private void dfs(List<Integer> list, int index, int sum) {
        if(sum + candidates[index] > target) {
            return;
        }
        sum += candidates[index];
        list.add(candidates[index]);
        if(sum == target) {
            res.add(new ArrayList<>(list));
        }
        for(int i = index; i < candidates.length; i++) {
            dfs(list, i, sum);
        }
        sum -= candidates[index];
        list.remove(list.size() - 1);
    }
}