java - 给定一堆整数，请仅使用加号运算输出所有可能数字的所有组合

Question

给定一堆整数，请仅使用加号运算输出所有可能数字的所有组合。

例如，

[10, 20] => [10, 20, 30]
[1, 2, 3] => [1, 2, 3, 4, 5, 6]
[10, 20, 20, 50] => [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

有人可以帮我用 Java 实现吗？

我已经尝试过并且我认为它可行，但正在寻找其他解决方案。

public int[] getCoins2(int[] coins) {
    Set<Integer> result = new TreeSet<>();

    for (int coin : coins) {
        result.addAll(result.stream().map(value -> value + coin).collect(Collectors.toSet()));
        result.add(coin);
    }

    return toInt(result);
}

public int[] toInt(Set<Integer> set) {
    int[] a = new int[set.size()];

    int i = 0;

    for (Integer val : set) {
        a[i++] = val;
    }

    return a;
}

public static void main(String[] args) {

    CoinCombination combination = new CoinCombination();
    int[] coins = {10, 20, 20, 50, 100};

    System.out.println(Arrays.toString(combination.getCoins2(coins)));
}

Answer 1

正如您在问题陈述中提到的:

please output all combination of all possible numbers by using plus operation only.

• 解决方案的时间复杂度将保持指数级，即 O(2^N-1)，因为我们必须尝试每个子序列数组的。

• 由于您使用的是 TreeSet，add 的复杂性将增加 log(n) 的开销，而 addAll() 将增加 O(m log (n)) 在最坏的情况下，其中 m 和 n 是每棵树中元素的数量。看这个answer .

• 从技术上讲，这会在每个步骤中增加 O(m log(n)) 的复杂性，使其成为 O(2^N - 1) * O(m log(n) ).

• 我建议您最好使用 HashSet，其中 add() 和 contains() 会给您一个 O(1 ) 平均性能(如果有碰撞可能会上升到 O(n)，但通常不是这种情况)。

• 这样，复杂度保持为 O(2^N-1)，最后有一个附加(不是乘法)排序开销(如果你 希望对其进行排序)这将是 O(m log m) 其中 m ~ 2^N - 1. 你也可以比较两种方法的运行时间。

代码:

import java.util.*;
public class CoinCombination {
        public List<Integer> getCoinSums(int[] coins) {
        Set<Integer> set = new HashSet<>();
        List<Integer> sums = new ArrayList<>();
        for (int coin : coins) {
            int size = sums.size(); 
            for(int j=0;j<size;++j){
                int new_sum = sums.get(j) + coin;
                if(!set.contains(new_sum)){
                    sums.add(new_sum);   
                    set.add(new_sum);
                }
            }
            if(!set.contains(coin)){
                sums.add(coin);
                set.add(coin);
            }
        }

        Collections.sort(sums);
        return sums;
    }

    public static void main(String[] args) {
        CoinCombination combination = new CoinCombination();
        int[][] coins = {
            {10,20},
            {1,2,3},
            {10, 20, 20, 50},
            {10, 20, 20, 50, 100}
        };
        for(int[] each_set_of_coins : coins){
            System.out.println(combination.getCoinSums(each_set_of_coins).toString());
        }        
    }
}

输出:

[10, 20, 30]
[1, 2, 3, 4, 5, 6]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200]