java - Sum 存在于数组项中

Question

建议我有以下数组:

{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，但似乎没有解决。

谢谢!

Answer 1

我的两分钱解决方案

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));
    }

}

将输出:

• 最大=10
  2 3 5
  4 6
• 最大=13
  2 5 6
  2 11
  3 4 6