如何找到求和到给定值可能集合

Question

给定一个arraylist和一个值，找出array中是否有一个和等于给定值的三元组。使用set找到了解决方案

我只想知道，如果我们不想找到三重，而是任何可能的数字，单重，双重，三重，四重奏，五重，六重，七重，会有什么逻辑。在本例中b表示

        long n = 12;
        long k = 8;
        int b = 3;

        List<Long> sticksOrder = new ArrayList<>();
        for (long l = 1; l <= k; l++){
            sticksOrder.add(l);
        }

        for (int i = 0; i < sticksOrder.size() - 2; i++) {
            Set<Long> s = new HashSet<>();
            long curr_sum = n - sticksOrder.get(i);
            for (int j = i + 1; j < sticksOrder.size(); j++)
            {
                if (s.contains(curr_sum - sticksOrder.get(j)))
                {
                    System.out.printf("Triplet is %d, %d, %d", sticksOrder.get(i), sticksOrder.get(j), curr_sum - sticksOrder.get(j));
                }
                s.add(sticksOrder.get(j));
            }
        }

Answer 1

你所描述的更广为人知的是背包问题。

它是NP完全的。意思是，如果你有一个高效的算法，那么两件事将会发生：

[1]有一大堆算法，比如旅行推销员，我可以这样写：“转换输入，使其成为一个背包问题，使用初学者惊人高效的背包问题求解器，现在我已经转换输入，使其看起来像一个背包问题，它可以快速解决我的问题，然后将我得到的答案转换回旅行推销员问题的答案；转换也可以是高效的，使整个管道变得高效”。换句话说，解决一个NP完全问题，然后全部解决；这就是np-complete的完整部分的含义（它包含所有NP域）。

这也意味着，如果你认为你有一个有效的方法来做这件事，或者如果你认为你可以采取一个有效的算法，并通过一些调整，你认为你可以把它变成一个保留其效率并可以解决背包问题的算法，那么要么[a]十亿美元，要么[B]不。

可能是[B]。

你粘贴的这个算法是高效的。因此，不能轻易地调整它来做你想做的事情--这种调整要么是如此不明显，以至于许多人都没有发现它，要么将算法转换成完全不同的东西（因为它必须是一个不太高效的算法）。