leetcode题目39. 组合总和（java）

题目描述

给定一个 无重复元素 的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字 可以无限制重复被选取。所有数字（包括 target）都是正整数。解集不能包含重复的组合。

示例

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
     [
     [7],
     [2,2,3]
     ]

输入：candidates = [2,3,5], target = 8,
所求解集为：
     [
     [2,2,2,2],
     [2,3,3],
     [3,5]
     ]

代码

/**
 * 参考：https://leetcode-cn.com/problems/combination-sum/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-m-2/
 */
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    Arrays.sort(candidates); // 排序
    dfs(candidates, target, result, path, 0);
    return result;
}

public void dfs(int[] candidates, int target, List<List<Integer>> result, LinkedList<Integer> path, int begin) {
    if (target == 0) {
        // 找到了一条路径，将路径拷贝一份儿放到结果数组里
        result.add(new ArrayList<Integer>(path));
        return;
    }
    for (int i = begin; i < candidates.length; i ++) {
        if (candidates[i] > target) {
            // 剪枝，去除没必要的搜索
            return;
        }
        path.add(candidates[i]);
        dfs(candidates, target - candidates[i], result, path, i); // 递归
        path.removeLast(); // 每次回溯将最后一次加入的元素删除
    }
}