题解 | #牛群分组II#

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;
            }
        }
    }
}