how can you find the length of the longest subset (powerset) with sum equal to k with least time complexity?

user_11307098 0
Viewed 513

Given an array of integers, I'm trying to find the longest subset (powerset) with sum equal to k using the lease possible time complexity. e.g. if inputArr= [1, 2, 8, 1, 1, 7] and k= 10, then the output should be 4 since the longest subset with sum equals to 10 is [1, 1, 1, 7].

Edit: I might've forgotten an important detail; the elements of the array are all positive and non-zero.

I used this algorithm that I found on geeksforgeeks: https://www.geeksforgeeks.org/finding-all-subsets-of-a-given-set-in-java/

The code works fine, but the only problem that I have is with the execution time. I am supposed to submit this online, and when I submit it the execution terminates due to timeout.

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

Is there any faster algorithm? I tried a recursive one and it didn't help.

powerset subset algorithm java
1 Answers

We can solve this with dynamic programming in O(n*k) time and O(k) space. JavaScript code:

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

user_20347870
Related