给定一个整数数组和一个整数 n，如何找到一个总和为 n 的子数组(非连续)

Question

我正在做一个练习，我不得不检查是否有办法在总和为给定整数 n 的排序数组中找到一个不连续的序列。

例如：

    int[] a = {1, 2, 4, 5, 10};
    int n = 20;

总和为 20 的整数位于位置 0、2、3、4。

我该怎么做？

Answer 1

你应该遍历一个集合的所有子集。对于带有 N 的集合，您可以有 Math.pow(2,N) 个子集。为此，您可以从 1 迭代到 Math.pow(2,N)，并尝试在位值为 1 的位置上添加一些元素，如果子集的总和为 K，则找到子集。