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;

    }
}

原文地址：https://blog.csdn.net/Chang_Yafei/article/details/142449039

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！