39. 组合总和-java

 这是一道回溯的题目，深度优先搜索，难点是如何去掉重复的组合，对于[2,3,6,7] target = 7,[2,2,3]和[3,2,2]是重复的组合。在选数的时候给予限制，比如说第一个数选了3，第二个数只可以选3之后的数，即[6,7]，如此可以限制重复的组合。

class Solution {

    List> ans;

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

        ans = new LinkedList<>();

        LinkedList l = new LinkedList<>();

        dfs(target, 0, l, candidates);

        return ans;

    }

    void dfs(int target, int begin, LinkedList l, int[] candidates) {

        //满足taget的一种组合数

        if(target == 0) {

            ans.add(new LinkedList(l));

            return;

        }

        //减枝，肯定不满足

        if(target < 0) {

            return;

        }

        System.out.println(target);

        //选数的下标是begin

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

            if(target >= candidates[i]) {

                l.add(candidates[i]);

                int temp = target - candidates[i];

                //下一次的begin穿的是当前层数的i，意味着下一次选数只能从i之后的位置选

                //避免出现重复的组合

                dfs(temp, i , l, candidates);

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

            }

        }

        return;

    }

}