LeetCode刷题实战39：组合总和
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 组合总和，我们先来看题面：
https://leetcode-cn.com/problems/combination-sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
题意
样例
输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：
输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]
题解
回溯法
以 target = 7 为根结点，每一个分支做减法。减到 0 或者负数的时候，剪枝。其中，减到 0 的时候结算，这里 “结算” 的意思是添加到结果集。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(candidates);
backtrack(candidates, target, res, 0, new ArrayList<Integer>());
return res;
}
private void backtrack(int[] candidates, int target, List<List<Integer>> res,
int i, ArrayList<Integer> tmp_list) {
if (target < 0) return;
if (target == 0) {
res.add(new ArrayList<>(tmp_list)); return;
}
for (int start = i; start < candidates.length; start++) {
if (target < candidates[start]) break;
tmp_list.add(candidates[start]);
backtrack(candidates, target - candidates[start], res, start, tmp_list);
tmp_list.remove(tmp_list.size() - 1);
}
}
}
上期推文：
赞 (0)