LeetCode程序员面试金典:组合总和 II

发布时间:2023-05-04 10:42:42

  题目:

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

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

  注:解集不能包含重复组合。

  示例1:[10,1,2,7,6,1,5]

  示例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); } }}

上一篇 LeetCode面试题:解码方法
下一篇 深入学习RabbitMQ五种模式(一)

文章素材均来源于网络,如有侵权,请联系管理员删除。

标签: Java教程Java基础Java编程技巧面试题Java面试题