题目:https://leetcode-cn.com/problems/combination-sum/submissions/
代码:
class Solution { public List<List<Integer>> combinationSum(int[] candidates, int target) { return this.handle(candidates, target, target); } private List<List<Integer>> handle(int[] candidates, int target, int maxCandidate) { List<List<Integer>> res = new ArrayList<>(); for (int c : candidates) { if (c > maxCandidate) { //避免重复组合 continue; } if (c == target) { //刚好相等,这个数直接是结果 List<Integer> list = new ArrayList<>(); list.add(c); res.add(list); } else if (c < target) { //小于,递归 List<List<Integer>> lists = this.handle(candidates, target - c, c); for (List<Integer> list : lists) { list.add(c); } res.addAll(lists); } } return res; } }
题目的意思其实就是把target这个数分解成candidates数组中的数,使用递归的做法即可实现,具体实现可以参考代码。
一个需要注意的点是为什么我递归的函数要增加一个maxCandidate的参数,这个参数主要的作用是用来组合去重。参考如下这么一个例子:
candidates=[2,3,6,7],target=7。
没有使用maxCandidate参数去重的话,得出结果为:[[3, 2, 2], [2, 3, 2], [2, 2, 3], [7]]。可以看到存在重复的组合,如果我们增加了maxCandidate参数结合代码中红色部分,那么我们可以控制组合结果一定是按照从小到大排列的,从而实现了去重效果,还去掉了多余的递归操作。