题解 | #牛群喂食#

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