39. Combination Sum

Question

39. Combination Sum

Solution

分析：以candidates = [2,3,5], target=8来分析这个问题的实现，反向思考，用target 8减2,3,5这三个数，等到target为0的时候，所减过的数就是我们要求的一个结果。

Java实现：

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates); // 排序
    search(candidates, target, result, new ArrayList<>(), 0);
    return result;
}

private void search(int[] candidates, int target, List<List<Integer>> ans, List<Integer> cur, int start) {
    if (target == 0) {
        ans.add(new ArrayList<>(cur)); // 浅拷贝
        return;
    }

    for (int i=start; i<candidates.length; i++) {
        if (candidates[i] > target) break;
        cur.add(candidates[i]);
        search(candidates, target - candidates[i], ans, cur, i);
        cur.remove(cur.size() - 1);
    }
}

Reference

• https://gitee.com/okokabcd/leetcode