#yyds干货盘点# leetcode算法题：组合总和 II

#yyds干货盘点# leetcode算法题：组合总和 II

题目：

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,

输出:

[

[1,1,6],

[1,2,5],

[1,7],

[2,6]

]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,

输出:

[

[1,2,2],

[5]

]

代码实现：

class Solution { List freq = new ArrayList(); List> ans = new ArrayList>(); List sequence = new ArrayList(); public List> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); for (int num : candidates) { int size = freq.size(); if (freq.isEmpty() || num != freq.get(size - 1)[0]) { freq.add(new int[]{num, 1}); } else { ++freq.get(size - 1)[1]; } } dfs(0, target); return ans; } public void dfs(int pos, int rest) { if (rest == 0) { ans.add(new ArrayList(sequence)); return; } if (pos == freq.size() || rest < freq.get(pos)[0]) { return; } dfs(pos + 1, rest); int most = Math.min(rest / freq.get(pos)[0], freq.get(pos)[1]); for (int i = 1; i <= most; ++i) { sequence.add(freq.get(pos)[0]); dfs(pos + 1, rest - i * freq.get(pos)[0]); } for (int i = 1; i <= most; ++i) { sequence.remove(sequence.size() - 1); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。