class Solution {

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

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

        if(candidates == null || candidates.length == 0) return res;

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

        return res;

    }

    //1.定义

    private void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> subset){

        //3.出口

        if(target == 0){

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

            return;

        }

        if(target < 0){

            return;

        }

        //2.拆解

        for(int i = index; i < candidates.length; i++){

            subset.add(candidates[i]);

            dfs(candidates, target - candidates[i], i, res, subset);

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

        }

    }

}

class Solution {

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

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

        if(candidates == null || candidates.length == 0) return res;

        Arrays.sort(candidates);

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

        return res;

    }

    private void dfs(int[] candidates, int target, int index, List<List<Integer>> res, List<Integer> subset){

        //出口

        if(target == 0){

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

            return;

        }

        if(target < 0){

            return;

        }

        //拆解

        for(int i = index; i < candidates.length; i++){

            if(i > index && candidates[i] == candidates[i - 1]) continue;

            subset.add(candidates[i]);

            dfs(candidates, target - candidates[i], i + 1, res, subset);

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

        }

    }

}