题解 | #牛群分组II#
牛群分组II
https://www.nowcoder.com/practice/9ebc32fee9b54bfa9f9c3deca80febb0
import java.util.*; public class Solution { static List<List<Integer>> res=new ArrayList<>(); public int[][] cowCombinationSum2 (int[] candidates, int target) { if (candidates==null||candidates.length<1){ return new int[][]{}; } boolean[] visited=new boolean[candidates.length]; dfs(candidates,target,visited,new ArrayList<>()); int[][] rs = new int[res.size()][];//转换结果 for (int i=0;i<res.size();i++){ rs[i]=new int[res.get(i).size()]; for (int j=0;j<rs[i].length;j++){ rs[i][j]=res.get(i).get(j); } } return rs; } public void dfs(int[] candidates, int target, boolean[] visited, ArrayList<Integer> list){ if (target==0){//basecase res.add(new ArrayList<>(list)); } if (target<0){//basecase return; } for (int i=0;i< candidates.length;i++){ if (list.size()>0&&candidates[i]< list.get(list.size()-1)){//剪枝条件,保证不重复 continue; } if (!visited[i]){ list.add(candidates[i]); visited[i]=true; dfs(candidates,target-candidates[i],visited,list); list.remove(list.size()-1); visited[i]=false; } } } }