如何找到总和等于 K 且时间复杂度最小的最长子集 (Powerset) 的长度?

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

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

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