总和存在于数组项中

user3150947 发表于 Dev

用户名

建议我有以下数组：

{2,3,4,5,11,6}并且我想知道数组的任何项是否包含数字x的总和。

例如：x = 10，则输出将为{2,3,5}和{4,6}。x = 13，则输出将为{2,11}，{3,4,6}和{2,5,6}

解决该问题的最佳算法是什么？

我已经考虑过使用数组的可能排列来解决此问题，并检查每个排列开始的总和是否等于X，但似乎无法解决。

谢谢！

尼罗河

我的两分钱的解决方案

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Test {

    public static void main(String[] args) {

        List<Integer> list = Arrays.asList(2, 3, 4, 5, 11, 6);
        Collections.sort(list);

        Integer sum = 0;
        Integer max = 13;

        for (int i=0; i<list.size(); i++) {
            sumNext(list, i, sum,max, new ArrayList<Integer>());
        }

    }

    private static void sumNext(List<Integer> list, int pos, Integer currentSum, Integer max,
            List<Integer> currentElement) {
        int nextSum = currentSum + list.get(pos);

        if (nextSum > max) {
            return;
        }

        currentElement.add(list.get(pos));
        if (nextSum == max) {
            for (Integer i : currentElement) {
                System.out.print(i);
                System.out.print(" ");
            }
            System.out.println();
        } else if (nextSum < max && list.get(pos) < max - currentSum) {
            // as array is sorted if current element is higher than the diff
            // between currentSum and max there is no need to try with next
            // element
            for (int i=pos+1; i<list.size(); i++) {
                sumNext(list, i, nextSum, max, currentElement);
            }
        }
        currentElement.remove(list.get(pos));
    }

}

将输出：