题解 | #牛群分组II#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param candidates int整型一维数组
     * @param target int整型
     * @return int整型二维数组
     */
    public static LinkedList<LinkedList<Integer>> lists = new LinkedList<>();
    public int[][] cowCombinationSum2 (int[] candidates, int target) {
       // write code here
        Boolean[] flags = new Boolean[candidates.length];
        Arrays.fill(flags,false);
        search(candidates,target,0,flags,new LinkedList<>());
        int[][] arr = new int[lists.size()][];
        for(int i=0;i<arr.length;i++){
            arr[i] = new int[lists.get(i).size()];
            for(int j=0;j<lists.get(i).size();j++){
                arr[i][j] = lists.get(i).get(j);
            }
        }
        return arr;
    }

    public void search(int[] nums,int target,int cur,Boolean[] flags,LinkedList<Integer> arrayList){
        if(cur==target){
            lists.add(new LinkedList<>(arrayList));
            return;
        }
        for(int i=0;i<flags.length;i++){
            if(!flags[i]){
                if(arrayList.size()!=0 && nums[i]<arrayList.get(arrayList.size()-1)){
                    continue;
                }
                arrayList.add(nums[i]);
                flags[i]=true;
                search(nums,target,cur+nums[i],flags,arrayList);
                arrayList.remove(arrayList.size()-1);
                flags[i] = false;
            }
        }
    }

}

本题考察的知识点主要N叉树的建立，所用编程语言为java.本题建立N叉树之后，需要考虑剪枝条件，不然含有重复的组合。重复的组合比如是（2,3,5），（3,5,2），（5,3,2），但是我们只能选择第一个，其余两个与第一个重复不应该算在满足条件的组合中。剪枝时我们考虑满足条件的组合，第一个元素如果比第二个元素大时，我们应该结束继续递归，进行剪枝。