Maximum multiple of D from K-sized subset sums from given Array

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:

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: 

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:

• Introduction to Dynamic Programming – Data Structures and Algorithm Tutorials