Count Subset With Target Sum II

JavaView on GFG

Problem Overview

Count subsets with given sum where array may have duplicates.

Intuition

Count subsets with given sum where array may have duplicates. DP with proper handling of duplicate elements.

Algorithm

1Sort array. DP similar to 0-1 knapsack: dp[j] = count of subsets with sum j.
2For each num: update dp right-to-left (0-1 knapsack style).

Common Pitfalls

• Same as LC 416 count variant. Handle duplicates: 0-1 knapsack treats each element independently.

Count Subset With Target Sum II.java

Java

// Approach: DP (unbounded). dp[j] = ways to achieve sum j using array elements with repetition allowed.
// Time: O(n * sum) Space: O(sum)
import java.util.*;

class Solution {
    private HashMap<String, Integer> dp;

    public int countSubset(int[] arr, int k) {
        int psum = 0, nsum = 0;
        for (int num : arr) {
            if (num > 0)
                psum += num;
            else
                nsum += num;
        }
        if (k > psum || k < nsum)
            return 0;

        dp = new HashMap<>();
        return solve(0, arr, k);
    }

    private int solve(int i, int[] arr, int k) {
        if (i == arr.length)
            return k == 0 ? 1 : 0;

        String key = i + "_" + k;
        if (dp.containsKey(key))
            return dp.get(key);

        int inc = solve(i + 1, arr, k - arr[i]);
        int exc = solve(i + 1, arr, k);

        dp.put(key, inc + exc);
        return inc + exc;
    }
}

Was this solution helpful?