题解 | #牛群分组II#
牛群分组II
https://www.nowcoder.com/practice/9ebc32fee9b54bfa9f9c3deca80febb0
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),但是我们只能选择第一个,其余两个与第一个重复不应该算在满足条件的组合中。剪枝时我们考虑满足条件的组合,第一个元素如果比第二个元素大时,我们应该结束继续递归,进行剪枝。