39. 组合总和 (opens new window)

1.dfs+回溯

分析：深度优先搜索，每一种元素只有选或者不选两种状态。本题难点在于如何去重。具体来说，怎么样保证搜索时只出现【2，2，3】这一组合，而不会出现【2，3，2】这一种组合？

这里采用递增的搜索策略来实现去重，通过index控制每次搜索的顺序，控制搜索时只能向后在【index，nums.length-1】之间获取数据，而不能向前搜索遍历。也就是说如果将3纳入当前队列后，在这棵子树下的所有分支主干都不能够选取2。

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res=new ArrayList<>();
        for(int i=0;i<candidates.length;i++){
            List<Integer> list=new ArrayList<Integer>();
            list.add(candidates[i]);
            dfs(list,candidates,target,candidates[i],i);
        }
        return res;
    }
    public void dfs(List<Integer> list,int[] candidates,int target,int curr,int index){
        if(curr>=target){
            if(curr==target){
                res.add(new ArrayList<>(list));
            }
            return ;
        }
        
        for(int i=index;i<candidates.length;i++){
            list.add(candidates[i]);
            dfs(list,candidates,target,curr+candidates[i],i);
            list.remove(list.size()-1);
        }
    }
}