穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞组合总和

 题目：

---

方法一：

解析： 

---

 

代码： 

private List<List<Integer>> ret;
    private List<Integer> path;
    private int aim; 

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        aim = target;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(candidates,0,0);

        return ret;
    }

    private void dfs(int[] candidates,int pos, int sum){
        if(sum == aim){
            ret.add(new ArrayList<>(path));
            return;
        } 

        if(aim < sum || pos == candidates.length) return;//剪枝二

        for(int i = pos; i < candidates.length; i++){
            path.add(candidates[i]);
            dfs(candidates,i, sum + candidates[i]);//剪枝一：从i开始往后选择
            path.remove(path.size()-1);
        }
    }

---

方法二： 

 

---

代码： 

 /**
    方法二：枚举元素个数 
    */ 

    private List<List<Integer>> ret;
    private List<Integer> path;
    private int aim; 

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        aim = target;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(candidates,0,0);

        return ret;
    }


    private void dfs(int[] candidates,int pos, int sum){
        if(sum == aim){
            ret.add(new ArrayList<>(path));
            return;
        } 

        if(aim < sum || pos == candidates.length) return;//剪枝二
        //k来枚举个数, candidates出现多少次
        for(int k = 0; k*candidates[pos] + sum <= aim; k++){
            if(k != 0) path.add(candidates[pos]);   
            dfs(candidates,pos+1,sum + k*candidates[pos]);
        }

        //回溯
        for(int k = 1; k*candidates[pos] + sum <= aim; k++)
            path.remove(path.size()-1);
    }