Given an integer array A[] of size N and two integers K, D. A list or superset of all possible subset sums of size K is made from the given array, the task is to find the largest multiple of D from this list or superset. If there exists no multiple, return -1 as the answer.
Examples:
Input: N = 4, K = 2, D = 2, A[] = [1, 2, 3, 4]
Output: 6
Explanation: All possible sums are [3, 4, 5, 5, 6, 7]. The greatest multiple of 2 is 6.Input: N = 4, K = 1, D = 3, A[] = [1, 5, 7, 8]
Output: -1
Explanation: All possible sums are [1, 5, 7, 8]. No multiple of 3 exists, hence return -1 as the answer.
Approach: To solve the problem using Recursive Top-Down Dp follow the below idea::
The main idea behind this solution is to break down the problem into smaller subproblems by considering each element of the array A. At each index i of the array A, we have two options – either include the element in one of the K subsets or exclude it. Thus, we can represent the problem as a tree of decisions, with each node representing the inclusion or exclusion of an element.
Steps that were to follow to implement the above approach:
- The countSubsetsRec function recursively calculates the maximum sum of a subset of a that contains exactly j elements and has a sum that is a multiple of D, where a is the input array of size N. The function takes the current index i, the number of chosen elements j, the current sum modulo D k, and the memoization table dp.
- The base case is when we have processed all N elements. If we have chosen exactly K elements and the sum is a multiple of D, we return 0, as we have found a valid subset. Otherwise, we return -INF to indicate that this state is impossible.
- We then check if the current state is already computed in the memoization table dp. If it is, we return the stored value.
- Otherwise, we calculate the maximum sum of a subset that contains exactly j elements and has a sum that is a multiple of D using the two possible transitions –
- one where we do not choose the current element and,
- one where we choose it.
- We take the maximum of these two transitions.
- Finally, we memoize the current state and return the result.
- The countSubsets function initializes the memoization table dp and calls countSubsetsRec with the initial parameters.
Below is the code to implement the above approach:
C++
// C++ code for the above approach.#include <bits/stdc++.h>using namespace std;// Main recursive function to return the// count of such subsets.long longcountSubsetsRec(int i, int j, int k, int N, int K, int D, vector<int>& a, vector<vector<vector<long long> > >& dp){ // Base case if (i == N) { if (j == K && k == 0) { return 0; } else { return INT_MIN; } } // Check if the current state // is already computed if (dp[i][j][k] != -1) { return dp[i][j][k]; } // Transition when A[i] isn't chosen long long ans = countSubsetsRec(i + 1, j, k, N, K, D, a, dp); // Transition when A[i] is chosen if (j != K) { ans = max(ans, countSubsetsRec(i + 1, j + 1, (k + a[i]) % D, N, K, D, a, dp) + a[i]); } // Memoize the current state dp[i][j][k] = ans; return ans;}long long countSubsets(int N, int K, int D, vector<int> a){ // Initializing the dp array vector<vector<vector<long long> > > dp( N + 1, vector<vector<long long> >( K + 1, vector<long long>(D, -1))); // Call the recursive function // and return the answer return countSubsetsRec(0, 0, 0, N, K, D, a, dp);}// Driver's codeint main(){ int N = 4, K = 2, D = 2; vector<int> a = { 1, 2, 3, 4 }; if (countSubsets(N, K, D, a) < 0) { cout << -1; return 0; } // Function call cout << countSubsets(N, K, D, a); return 0;} |
Java
// Java code for the above approach.import java.io.*;import java.util.*;class GFG { // main recursive function to return the count of such // subsets. static long countSubsetsRec(int i, int j, int k, int N, int K, int D, int[] a, long[][][] dp) { // Base case if (i == N) { if (j == K && k == 0) { return 0; } else { return Integer.MIN_VALUE; } } // Check if the current state is already computed if (dp[i][j][k] != -1) { return dp[i][j][k]; } // Transition when A[i] isn't chosen long ans = countSubsetsRec(i + 1, j, k, N, K, D, a, dp); // Transition when A[i] is chosen if (j != K) { ans = Math.max(ans, countSubsetsRec(i + 1, j + 1, (k + a[i]) % D, N, K, D, a, dp) + a[i]); } // Memoize the current state dp[i][j][k] = ans; // Return the answer. return ans; } static long countSubsets(int N, int K, int D, int[] a) { // Initializing the dp array long[][][] dp = new long[N + 1][K + 1][D]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { Arrays.fill(dp[i][j], -1); } } // Call the recursive function and return the answer long ans = countSubsetsRec(0, 0, 0, N, K, D, a, dp); if (ans < 0) { return -1; } else { return ans; } } public static void main(String[] args) { int N = 4, K = 2, D = 2; int[] a = { 1, 2, 3, 4 }; if (countSubsets(N, K, D, a) < 0) { System.out.println("-1"); return; } // Function call System.out.println(countSubsets(N, K, D, a)); }}// This code is contributed by sankar. |
Python3
# Python code for the above approach# Main recursive function to return the# count of such subsets.def countSubsetsRec(i, j, k, N, K, D, a, dp): # Base case if i == N: if j == K and k == 0: return 0 else: return float('-inf') # Check if the current state # is already computed if dp[i][j][k] != -1: return dp[i][j][k] # Transition when A[i] isn't chosen ans = countSubsetsRec(i + 1, j, k, N, K, D, a, dp) # Transition when A[i] is chosen if j != K: ans = max(ans, countSubsetsRec(i + 1, j + 1, (k + a[i]) % D, N, K, D, a, dp) + a[i]) # Memoize the current state dp[i][j][k] = ans return ansdef countSubsets(N, K, D, a): # Initializing the dp array dp = [[[-1 for i in range(D)] for j in range(K + 1)] for k in range(N + 1)] # Call the recursive function # and return the answer ans = countSubsetsRec(0, 0, 0, N, K, D, a, dp) if ans < 0: return -1 else: return ans# Driver's codeif __name__ == '__main__': N = 4 K = 2 D = 2 a = [1, 2, 3, 4] print(countSubsets(N, K, D, a))# This Code is Contributed by Shivam Tiwari |
C#
// C# program to find the maximum sum of a// subset such that no two elements in the// subset have a common factor greater than 1.using System;class GFG { // Function to return the maximum sum of a // subset such that no two elements in the // subset have a common factor greater than 1. static long countSubsets(int N, int K, int D, int[] a) { // Initializing the dp array long[, , ] dp = new long[N + 1, K + 1, D]; for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k < D; k++) { dp[i, j, k] = -1; } } } // Call the recursive function and return the answer long ans = countSubsetsRec(0, 0, 0, N, K, D, a, dp); if (ans < 0) { return -1; } else { return ans; } } // main recursive function to return the count of such // subsets. static long countSubsetsRec(int i, int j, int k, int N, int K, int D, int[] a, long[, , ] dp) { // Base case if (i == N) { if (j == K && k == 0) { return 0; } else { return Int32.MinValue; } } // Check if the current state is already computed if (dp[i, j, k] != -1) { return dp[i, j, k]; } // Transition when A[i] isn't chosen long ans = countSubsetsRec(i + 1, j, k, N, K, D, a, dp); // Transition when A[i] is chosen if (j != K) { ans = Math.Max(ans, countSubsetsRec(i + 1, j + 1, (k + a[i]) % D, N, K, D, a, dp) + a[i]); } // Memoize the current state dp[i, j, k] = ans; // Return the answer. return ans; } // Driver code public static void Main() { int N = 4, K = 2, D = 2; int[] a = { 1, 2, 3, 4 }; if (countSubsets(N, K, D, a) < 0) { Console.WriteLine("-1"); return; } // Function call Console.WriteLine(countSubsets(N, K, D, a)); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Main recursive function to return the// count of such subsets.function countSubsetsRec(i, j, k, N, K, D, a, dp) { // Base case if (i === N) { if (j === K && k === 0) { return 0; } else { return Number.MIN_SAFE_INTEGER; } } // Check if the current state // is already computed if (dp[i][j][k] !== -1) { return dp[i][j][k]; } // Transition when A[i] isn't chosen let ans = countSubsetsRec(i + 1, j, k, N, K, D, a, dp); // Transition when A[i] is chosen if (j !== K) { ans = Math.max(ans, countSubsetsRec(i + 1, j + 1, (k + a[i]) % D, N, K, D, a, dp) + a[i]); } // Memoize the current state dp[i][j][k] = ans; return ans;}function countSubsets(N, K, D, a) { // Initializing the dp array const dp = new Array(N + 1).fill(null).map(() => new Array(K + 1).fill(null).map(() => new Array(D).fill(-1)) ); // Call the recursive function // and return the answer return countSubsetsRec(0, 0, 0, N, K, D, a, dp);}// Driver's code const N = 4, K = 2, D = 2; const a = [1, 2, 3, 4]; if (countSubsets(N, K, D, a) < 0) { console.log(-1); } // Function call console.log(countSubsets(N, K, D, a)); |
Output
6
Time Complexity: O(NKD), since we are doing nested iteration N*K*D times.
Auxiliary Space: O(NKD), for creating the dp array.
Approach: To solve the problem using the Bottom-up Dp approach follow the below idea:
Let’s define dp[i][j][k] as the maximum sum of j elements chosen out of A[1], A[2], ….., A[i] such that the remainder when the sum is divided by D is k (or −1 if it is impossible).
Now there can be two cases:
- Skip the current elements, we can update the dp as:
- dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k])
- Take the current element, we can update the dp as:
- dp[i + 1][j + 1][(k + a[i]) % D] = max(dp[i + 1][j + 1][(k + a[i]) % D], dp[i][j][k] + a[i])
The final answer is stored in state dp[n][k][0].
Steps that were to follow the above approach:
- Initialize a dp array of (N+1)*(K+1)*(D) size with all states as -1, and dp[0][0][0] = 0.
- Now iterate for i in the range [0, N), for j in the range [0, K], and for k in the range [0, D).
- If dp[i][j][k] = -1, then this state is not reachable.
- Otherwise, we can do the transition as mentioned.
- For the second case where we have to choose the element, check if the number of chosen elements till now is not equal to K, i.e., j != K.
- Return the final answer as dp[n][k][0].
Below is the code to implement the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to return the count of subsets// divisible by D, and of size K.int countSubsets(int N, int K, int D, vector<int> a){ // Initializing the dp array long long dp[N + 1][K + 1][D]; // Setting all states to -1. memset(dp, -1, sizeof(dp)); dp[0][0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < K + 1; j++) { for (int k = 0; k < D; k++) { // This state is not // achievable. if (dp[i][j][k] == -1) continue; // Transition when A[i] // isn't chosen dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]); // Transition when A[i] // is chosen if (j != K) { dp[i + 1][j + 1][(k + a[i]) % D] = max( dp[i + 1][j + 1][(k + a[i]) % D], dp[i][j][k] + a[i]); } } } } // Returning the answer. return dp[N][K][0];}// Driver's codeint main(){ int N = 4, K = 2, D = 2; vector<int> a = { 1, 2, 3, 4 }; // Function call cout << countSubsets(N, K, D, a); return 0;} |
Python3
# Python code for the above approachdef countSubsets(N, K, D, a): # Initializing the dp array dp = [[[-1 for _ in range(D)] for _ in range(K+1)] for _ in range(N+1)] dp[0][0][0] = 0 for i in range(N): for j in range(K+1): for k in range(D): # This state is not achievable. if dp[i][j][k] == -1: continue # Transition when A[i] isn't chosen dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k]) # Transition when A[i] is chosen if j != K: dp[i+1][j+1][(k+a[i]) % D] = max(dp[i+1][j+1] [(k+a[i]) % D], dp[i][j][k] + a[i]) # Returning the answer return dp[N][K][0]# Driver's codeN = 4K = 2D = 2a = [1, 2, 3, 4]# Function callprint(countSubsets(N, K, D, a))# This code is contributed by Sakshi |
C#
// C# code for the above approachusing System;class Program{ // Function to return the count of subsets // divisible by D, and of size K. static int CountSubsets(int N, int K, int D, int[] a) { // Initializing the dp array long[,,] dp = new long[N + 1, K + 1, D]; // Setting all states to -1. for (int i = 0; i <= N; i++) { for (int j = 0; j <= K; j++) { for (int k = 0; k < D; k++) { dp[i, j, k] = -1; } } } dp[0, 0, 0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < K + 1; j++) { for (int k = 0; k < D; k++) { // This state is not // achievable. if (dp[i, j, k] == -1) continue; // Transition when A[i] // isn't chosen dp[i + 1, j, k] = Math.Max(dp[i + 1, j, k], dp[i, j, k]); // Transition when A[i] // is chosen if (j != K) { dp[i + 1, j + 1, (k + a[i]) % D] = Math.Max( dp[i + 1, j + 1, (k + a[i]) % D], dp[i, j, k] + a[i]); } } } } // Returning the answer. return (int)dp[N, K, 0]; } // Driver's code static void Main(string[] args) { int N = 4, K = 2, D = 2; int[] a = { 1, 2, 3, 4 }; // Function call Console.WriteLine(CountSubsets(N, K, D, a)); }} |
Output
6
Time Complexity: O(N*K*D), since we are doing nested iteration N*K*D times.
Auxiliary Space: O(N*K*D), for creating the dp array.
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
