Leetcode 39. 组合总和

题目链接 https://leetcode-cn.com/problems/combination-sum/

深度优先搜索、回溯、剪枝。

参照[liweiliwei1419的题解](回溯算法 + 剪枝（回溯经典例题详解） - 组合总和 - 力扣（LeetCode） (leetcode-cn.com))，如果candidates = [2,3,6,7], target = 7，先画出类似如下的树形图，边上的数值为candidates的元素，从根到所有为0的节点的路径就是合法路径。深度优先搜索到节点为0或者为负数时停止该分支上的搜索（后续可以排序candidates进行剪枝）。

存储搜索路径的数据结构使用双向队列，在递归完成对当前节点的深度优先搜索后需要removeLast来reset路径状态回到搜索之前。

在搜索某一节点时，每一个分支的搜索起始点需要在candidates中向后移动一个位置，以避免使用同一层已经使用过的元素导致结果出现重复。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        if(len == 0) {
            return res;
        }
        Deque<Integer> path = new ArrayDeque<>();
        dfs(res, candidates, target, 0, path, len);
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] candidates, int target, int begin,
                    Deque<Integer> path, int len) {
      
        if(target < 0) {
            return;
        }
        if(target == 0) {
            res.add(new ArrayList<>(path));
        }
        for(int i = begin; i < len; i++) {
            path.addLast(candidates[i]);
            dfs(res, candidates, target - candidates[i], i, path, len);
            path.removeLast();
        }
    }
}

剪枝：排序数组，当下一节点已经为负数时，这个节点就不再往下搜索了。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        int len = candidates.length;
        if(len == 0) {
            return res;
        }
        Arrays.sort(candidates);
        Deque<Integer> path = new ArrayDeque<>();
        dfs(res, candidates, target, 0, path, len);
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] candidates, int target, int begin,
                    Deque<Integer> path, int len) {
      
        if(target == 0) {
            res.add(new ArrayList<>(path));
        }
        for(int i = begin; i < len; i++) {
            if(target - candidates[i] < 0) {
                break;
            }
            path.addLast(candidates[i]);
            dfs(res, candidates, target - candidates[i], i, path, len);
            path.removeLast();
        }
    }
}