Count Number of subsets and given difference

Problem Statement

Given an array arr[] of size n and a difference value diff, count the number of subsets S1 and S2 such that:

|sum(S1) - sum(S2)| = diff

Transformation to Subset Sum

Let total sum be sum.

We want to partition into two subsets such that:

S1 - S2 = diff   --- (1)
S1 + S2 = sum    --- (2)

Add (1) and (2):

2S1 = diff + sum
=> S1 = (diff + sum)/2

So, the problem reduces to:

Count the number of subsets with sum = (diff + sum) / 2.

Let target = (diff + sum) / 2.
If (diff + sum) is odd, no such partition exists.

Step 1: Recursion (IBH + Pick / Not Pick)

IBH Pattern

Recursive Code (Java)

class Solution {
    public int countSubsetsRec(int[] arr, int index, int target) {
        // Base Case
        if (index == 0) {
            if (target == 0 && arr[0] == 0) return 2; // pick & not pick
            if (target == 0 || arr[0] == target) return 1;
            return 0;
        }

        // Not Pick
        int notPick = countSubsetsRec(arr, index - 1, target);

        // Pick (only if arr[index] <= target)
        int pick = 0;
        if (arr[index] <= target) {
            pick = countSubsetsRec(arr, index - 1, target - arr[index]);
        }

        return pick + notPick;
    }
}

Choice Diagram

                        f(i, target)
                       /            \
                 f(i-1, target)    f(i-1, target - arr[i])
                 (not pick)            (pick)

Time Complexity (Recursion)

TC = O(2^n)
SC = O(n)  // recursion stack

Step 2: Memoization (Top Down)

class Solution {
    public int countSubsetsMemo(int[] arr, int index, int target, Integer[][] dp) {
        if (index == 0) {
            if (target == 0 && arr[0] == 0) return 2;
            if (target == 0 || arr[0] == target) return 1;
            return 0;
        }

        if (dp[index][target] != null) return dp[index][target];

        int notPick = countSubsetsMemo(arr, index - 1, target, dp);
        int pick = 0;
        if (arr[index] <= target) {
            pick = countSubsetsMemo(arr, index - 1, target - arr[index], dp);
        }

        return dp[index][target] = pick + notPick;
    }
}

Time and Space (Memoization)

TC: O(n * target)
SC: O(n * target) + O(n) recursion stack

Step 3: Tabulation (Bottom-Up DP)

class Solution {
    public int countSubsetsTab(int[] arr, int diff) {
        int sum = 0;
        for (int num : arr) sum += num;

        if ((sum + diff) % 2 != 0) return 0;

        int target = (sum + diff) / 2;
        int n = arr.length;

        int[][] dp = new int[n][target + 1];

        // Base Cases
        if (arr[0] == 0) dp[0][0] = 2; // pick & not pick
        else dp[0][0] = 1;

        if (arr[0] != 0 && arr[0] <= target) {
            dp[0][arr[0]] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int t = 0; t <= target; t++) {
                int notPick = dp[i - 1][t];
                int pick = 0;
                if (arr[i] <= t) {
                    pick = dp[i - 1][t - arr[i]];
                }
                dp[i][t] = pick + notPick;
            }
        }

        return dp[n - 1][target];
    }
}

Time and Space (Tabulation)

TC: O(n * target)
SC: O(n * target)

Step 4: Space Optimization

class Solution {
    public int countSubsetsSO(int[] arr, int diff) {
        int sum = 0;
        for (int num : arr) sum += num;

        if ((sum + diff) % 2 != 0) return 0;

        int target = (sum + diff) / 2;
        int n = arr.length;

        int[] prev = new int[target + 1];

        if (arr[0] == 0) prev[0] = 2;
        else prev[0] = 1;

        if (arr[0] != 0 && arr[0] <= target) {
            prev[arr[0]] = 1;
        }

        for (int i = 1; i < n; i++) {
            int[] curr = new int[target + 1];
            for (int t = 0; t <= target; t++) {
                int notPick = prev[t];
                int pick = 0;
                if (arr[i] <= t) {
                    pick = prev[t - arr[i]];
                }
                curr[t] = pick + notPick;
            }
            prev = curr;
        }

        return prev[target];
    }
}

Final Notes