题解 | #牛群喂食# Java

使用回溯算法来找到所有可能的组合。我们从第一个元素开始，如果它小于等于目标值，就将其加入临时列表中，并递归调用回溯函数，将目标值减去当前元素的值。当目标值为0时，说明找到了一组解，将其加入结果列表中。最后，我们将结果列表转换为二维数组并返回。

import java.util.*;


public class Solution {

    public int[][] cowCombinationSum (int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);

        backTrack(ans, new ArrayList<>(), candidates, target, 0);

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

    void backTrack(List<List<Integer>> ans, List<Integer> an, int[] candidates,
                   int target, int start) {
        if (target == 0) {
            ans.add(new ArrayList<>(an));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] <= target) {
                an.add(candidates[i]);
                backTrack(ans, new ArrayList<>(an), candidates, target - candidates[i], i);;
                an.remove(an.size() - 1);
            }
        }
    }
}