如何以最小的时间复杂度找到子集（幂集）中和为k的最长子集的长度？

Question

给定一个整数数组，我正在尝试找到最长的子集（幂集），使其总和等于k，使用最少的时间复杂度。 例如，如果inputArr = [1, 2, 8, 1, 1, 7]且k = 10，则输出应为4，因为总和等于10的最长子集是[1, 1, 1, 7]。 编辑：我可能忘记了一个重要细节; 数组的元素都是正数且非零。 我使用了在geeksforgeeks上找到的这个算法： https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/ 代码可以正常工作，但我唯一的问题是执行时间。 我应该在线提交它，但当我提交时，由于超时而终止执行。

    int maxSubLength=0;
    for (int i = 1; i < (1<<n); i++)   //n is the length of inputArr
    {
        int sum=0, length=0;

        for (int j = 0; j < n; j++)
          if ((i & (1 << j)) > 0)
          {
                sum+=inputArr[j];
                length++;
                if (sum>k)
                   break;
          }  

        if (sum==k)
            maxSubLength=Math.max(maxSubLength, length);
    }

有更快的算法吗？我尝试了递归算法，但并没有帮助。

- Jim

---

没有快速的方法可以生成一个大集合的所有子集，因为一个大小为 n 的集合有 2ⁿ 个超集。您能发布您正在尝试解决的问题的完整文本，包括对集合大小和/或其值的任何限制吗？ - ruakh

@ruakh 我可能忘记了一个重要的细节; 数组的元素都是正数且非零。以下是问题的完整文本： “给定一个由n个正非零整数组成的数组，找到和为k的整数最长子集的长度。”其中1<=n<=1000，1<=k<=2000...。对于较大的n值，上述代码会导致溢出问题。但我使用BigInteger解决了这个问题，我只是不想过于复杂化这个问题。 - Jim

换句话说，你需要达到什么时间复杂度的大O符号表示法？ - Josh W.

@JoshW。我真的不确定。问题没有指定，而且我也不知道这个问题可以在什么时间复杂度下解决。 - Jim

似乎这是一个子集求和问题，需要额外的要求来找到可能的最大子集，使其总和等于给定值。可以通过对子集求和算法进行轻微修改来解决它，其运行时间肯定比计算所有子集要好。 - jrook

Answer 1

我们可以使用动态规划来解决这个问题，时间复杂度为 O(n*k)，空间复杂度为 O(k)。以下是 JavaScript 代码：

function f(A, K){
  let m = new Array(K + 1).fill(0)
    
  for (let a of A){
    for (let k=K; k>=a; k--)
      if (m[k - a])
        m[k] = Math.max(m[k], 1 + m[k - a])

    m[a] = Math.max(m[a], 1)
  }
  
  return m[K]
}

var A = [1, 2, 8, 1, 1, 7]
var K = 10

console.log(f(A, K))

- גלעד ברקן

---

非常感谢你，伙计！这真的帮了我很多！ - Jim