Sum of length of two smallest subsets possible from a given array with sum at least K

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e9;

  

int MinimumLength(int A[], int N, int K)

{

    

    sort(A, A + N);

  

    

    int suffix[N + 1] = { 0 };

  

    

    for (int i = N - 1; i >= 0; i--)

        suffix[i] = suffix[i + 1] + A[i];

  

    

    int dp[N + 1][K + 1];

  

    

    

    for (int i = 0; i <= N; i++)

        for (int j = 0; j <= K; j++)

            dp[i][j] = MAX;

  

    

    dp[N][0] = 0;

  

    

    for (int i = N - 1; i >= 0; i--) {

  

        

        for (int j = K; j >= 0; j--) {

  

            

            

            

            if (j <= A[i]) {

                dp[i][j] = A[i];

                continue;

            }

  

            

            

            if (dp[i + 1][j - A[i]] == MAX)

                dp[i][j] = MAX;

  

            

            

            

            

            else

                dp[i][j] = min(dp[i + 1][j],

                               dp[i + 1][j - A[i]] + A[i]);

        }

    }

  

    

    for (int i = N - 1; i >= 0; i--) {

  

        

        if (suffix[i] - dp[i][K] >= K) {

  

            

            

            return N - i;

        }

    }

  

    

    

    return -1;

}

  

int main()

{

    int arr[] = { 7, 4, 5, 6, 8 };

    int K = 13;

    int N = sizeof(arr) / sizeof(arr[0]);

  

    cout << MinimumLength(arr, N, K);

  

    return 0;

}

Let's block ads! (Why?)