Leetcode面试经典150题-39.组合总数进阶：40.组合总和II

本题是扩展题，真实考过，看这个题之前先看一下39题

Leetcode面试经典150题-39.组合总数-CSDN博客

给定一个候选人编号的集合 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]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

其他的就不多说了，上代码，看不懂的请留言或者私信，收到第一时间解答

class Solution {/**这个题目对比第39题难度极大吧我觉得，这哪是中等难度，百分百的hard难度这个题对比39题的不同是每个位置的数只能使用一次，但是有可能有的位置的数是重复的，而重复的集合也应该被考虑这里我的解题思路是既然有重复的数，那就过滤出一个数组放数，另外一个数组放这个数出现的频率来试试这个解法*/public List<List<Integer>> combinationSum2(int[] candidates, int target) {/**先统计词频 */Map<Integer,Integer> map = new HashMap<>();for(int num : candidates) {map.put(num, map.getOrDefault(num, 0) + 1);}/**统计完词频之后把原来的数组分为两个数组，这里我想先排序，所以这里先统计出数字数组，稍后再统计词频数组 */int[] nums = new int[map.keySet().size()];int curIndex = 0;for(int num : map.keySet()) {nums[curIndex ++] = num;}/**排个序用于剪枝*/Arrays.sort(nums);/**统计词频数组 */int[] counts = new int[nums.length];for(int i = 0; i < nums.length; i++) {counts[i] = map.get(nums[i]);}return process(nums, counts, 0, target);}public List<List<Integer>> process(int[] nums, int[] counts, int curIndex, int targetLeft) {List<List<Integer>> ans = new ArrayList<>();if(targetLeft == 0) {ans.add(new ArrayList<>());return ans;}/**如果targetLeft不为0，但是我们没有数了，失败，返回空集合 */if(curIndex == nums.length) {return ans;}/**我们是按照从小到大排序的数组，如果targetLeft已经比当前数小了也没必要继续尝试了 */if(targetLeft < nums[curIndex]) {return ans;}/**其他情况正常尝试,当前数可以尝试Math.min(count[curIndex], targetLeft/nums[curIndex])次*/for(int i = 0; i <= Math.min(counts[curIndex], targetLeft/nums[curIndex]); i++) {List<List<Integer>> next = process(nums, counts, curIndex + 1, targetLeft - i * nums[curIndex]);for(List<Integer> list : next) {/**当前数加了多少个，就加入多少个到next中的集合中，因为确实是使用了这么多个 */for(int num = 0; num < i; num ++) {list.add(nums[curIndex]);}/**加入到当前数的集合 */ans.add(list);}}return ans;}
}