39. Combination Sum

Question

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

巴特西

39. Combination Sum - LeetCode

Question

Solution

Reference

最新文章

热门文章