题解 | #牛群喂食#

知识点

回溯

解题思路

题目的题意是，要找出 candidates 中可以使食物总量和为目标数 target 的所有不同组合，我们可以使用回溯算法。

回溯算法通过不断尝试不同的选择，然后回溯到上一步进行下一个选择，来找到所有可能的组合。

Java题解

import java.util.*;


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

    private void backtrack(List<List<Integer>> result, List<Integer> combination,
                           int[] candidates, int target, int start) {
        if (target == 0) {
            result.add(new ArrayList<>(combination));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            int num = candidates[i];
            if (target - num < 0) {
                break; // 因为数组已经排序，后续的数字肯定会更大，所以直接结束循环
            }
            combination.add(num);
            backtrack(result, combination, candidates, target - num,
                      i); // 可以重复选择当前数字，所以传入的参数仍然是 i
            combination.remove(combination.size() - 1);
        }
    }

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