DAY 17 - Minimum sum partition

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-17.

I am also looking for guidance in C++ , compilers and LLMs. Any help would be highly appreciated.

Problem: Minimum sum partition

Given an array arr of size n containing non-negative integers, the task is to divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum and find the minimum difference

Example 1:

Input: N = 4, arr[] = {1, 6, 11, 5}
Output: 1
Explanation:
Subset1 = {1, 5, 6}, sum of Subset1 = 12
Subset2 = {11}, sum of Subset2 = 11

Intuition: I think we have got it until now what we do in problems like this.

We will use recursion to form a relation and the optimize it using Dynamic Programming.
It is important to understand what we did in the previous question of the Subset Sum equal to the target. There we found whether or not a subset exists in an array with a given target sum. We used a dp array to get to our answer.

Important:

We used to return dp[n-1][k] as our answer. One interesting thing that is happening is that for calculating our answer for dp[n-1][k], we are also solving multiple sub-problems and at the same time storing them as well. We will use this property to solve the question of this article.

Approach: Recursion + Memoization

• Calculate totalSum using for loop.
• At every step we don't need to calculate sum of both partitions, We will simply calculate one partition's and subtract the other from total sum.
• Apply the observation into an if case.
• Base Case establishment: Start from the last index.
• If we have reached our required sum/target, we return true.
• If we have reached the end of our iteration in a recursive way, just see if the last index leads to our target.
• Now that we have established base cases, let's form the recursive relation.(Observe what's changing and what we need at every step).
• We need an index, our target and the array of values.
• Two Options: Take the element in subset or not.
• Not Taken: We just decrement the index.
• Taken: First we need to see if target >= arr[index]. Then if it is: We decrement the index and update target.
• return taken || notTaken.
• We will also use a DP vector to memoize it all together as the question requires us to keep an update of the other partition and sum as well.

Code:

#include <bits/stdc++.h>

using namespace std;

int minSubsetSumDifference(vector < int > & arr, int n) {
  int totSum = 0;

  for (int i = 0; i < n; i++) {
    totSum += arr[i];
  }

  vector < vector < bool >> dp(n, vector < bool > (totSum + 1, false));

  for (int i = 0; i < n; i++) {
    dp[i][0] = true;
  }

  if (arr[0] <= totSum)
    dp[0][totSum] = true;

  for (int ind = 1; ind < n; ind++) {
    for (int target = 1; target <= totSum; target++) {

      bool notTaken = dp[ind - 1][target];

      bool taken = false;
      if (arr[ind] <= target)
        taken = dp[ind - 1][target - arr[ind]];

      dp[ind][target] = notTaken || taken;
    }
  }

  int mini = 1e9;
  for (int i = 0; i <= totSum; i++) {
    if (dp[n - 1][i] == true) {
      int diff = abs(i - (totSum - i));
      mini = min(mini, diff);
    }
  }
  return mini;
}

Complexity Analysis:
Time Complexity: O(N*totSum) + O(N) + O(N).
Space Complexity: O(N) + O(N*totSum)

I will be uploading the tabulation code and space optimization code shortly.
Thanks for reading. Feedback is highly appreciated.