面试算法82:包含重复元素集合的组合

2024-01-02 16:39:03

题目

给定一个可能包含重复数字的整数集合,请找出所有元素之和等于某个给定值的所有组合。输出中不得包含重复的组合。例如,输入整数集合[2,2,2,4,3,3],元素之和等于8的组合有2个,分别是[2,2,4]和[2,3,3]。

分析

避免重复的组合的方法是当在某一步决定跳过某个值为m的数字时,跳过所有值为m的数字。例如,假设求[2,2,2]的组合,如果在处理第1个2时决定跳过它并跳过所有的2,那么得到的是一个空的组合。如果选择第1个2之后决定跳过第2个2并连带跳过后面的2,那么得到的是组合[2]。如果选择前两个2之后决定跳过第3个2,那么得到的是组合[2,2]。如果3个2都被选择,则得到组合[2,2,2]。采用这个办法就可以避免产生重复的组合,如避免了两种产生重复组合[2,2]的情形,一种情形是跳过第1个2选择后面两个2,另一种情形是跳过中间一个2选择前后两个2。
为了方便跳过后面所有值相同的数字,可以将集合中的所有数字排序,把相同的数字放在一起,这样方便比较数字。当决定跳过某个值的数字时,可以按顺序扫描后面的数字,直到找到不同的值为止。

public class Test {
    public static void main(String[] args) {
        int[] nums = {2, 2, 2, 4, 3, 3};
        List<List<Integer>> result = combinationSum2(nums, 8);
        for (List<Integer> item : result) {
            System.out.println(item);
        }
    }

    public static List<List<Integer>> combinationSum2(int[] nums, int target) {
        Arrays.sort(nums);

        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        helper(nums, target, 0, combination, result);
        return result;
    }

    private static void helper(int[] nums, int target, int i, LinkedList<Integer> combination,
        List<List<Integer>> result) {
        if (target == 0) {
            result.add(new LinkedList<>(combination));
        }
        else if (target > 0 && i < nums.length) {
            helper(nums, target, getNext(nums, i), combination, result);

            combination.addLast(nums[i]);
            helper(nums, target - nums[i], i + 1, combination, result);
            combination.removeLast();
        }
    }

    private static int getNext(int[] nums, int index) {
        int next = index;
        while (next < nums.length && nums[next] == nums[index]) {
            next++;
        }

        return next;
    }
}

文章来源:https://blog.csdn.net/GoGleTech/article/details/135342440
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。