public class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        List<List<Integer>> res=new ArrayList<List<Integer>>();

        Arrays.sort(candidates);

        work(target,0,candidates,res,new ArrayList<Integer>());

        return res;

    }

    //胜读遍历，找出合格的数据

    /*

     * target：代表目标数据

     * index:代表循环的其实位置，也就是查找合格数据的额起始位置

     * candidates 候选值数组

     * res:返回值

     * arrayList：保存一组合格数据的变量

     * */

    public void work(int target, int index, int[] candidates, List<List<Integer>> res, ArrayList<Integer> arrayList){

        //for循环，每次从index出发，因为数组已经排序，所以不会出现重复的数据

        //终止条件为索引越界&&目标值要大于等于当前要检查的候选值

        for(int i=index;i<candidates.length&&candidates[i]<=target;i++){

            /*

             * 如果target大于当前从candidate中提取的值时，则可以将其加入到arrayList中，在进入深度的遍历查找合格数据

             * 注意的是，当无论是查找成功还是失败的时候，都要将arrayList的最后一个数据弹出，一遍进行下一次的深度遍历

             * */

            if(candidates[i]<target){

                arrayList.add(candidates[i]);

                work(target-candidates[i], i+1, candidates, res, arrayList);

                arrayList.remove(arrayList.size()-1);

            }

            /*

             * 如果target==当前提取的candidate中的值，则表明查找成功，将这一数组添加到res横中

             * 并且弹出弹出arrayList中的最后一个数据进行下一次的遍历

             * */

            else if(candidates[i]==target){

                arrayList.add(candidates[i]);

                if(!check(arrayList,res))

                    res.add(new ArrayList<Integer>(arrayList));

                arrayList.remove(arrayList.size()-1);

            }

        }

    }

    public boolean check(ArrayList<Integer> arrayList, List<List<Integer>> res){

        ArrayList<Integer> temp;

        int count=0;

        for(int i=0;i<res.size();i++){

            temp=(ArrayList<Integer>) res.get(i);

            count=0;

            if(temp.size()==arrayList.size()){

                for(int j=0;j<temp.size();j++){

                    if(temp.get(j)==arrayList.get(j))count++;

                }

                if(count==arrayList.size())return true;

            }

        }

        return false;

    }

}