Count the number of subset with a given difference || DP problem variation || Asked in interview
7441

Given in question :

  1. an array (arr)
  2. a difference (diff)

Task: To find count of all arrays whose difference is equal to diff.

Theory

assume we find 2 subsets S1 and S2 whose:-
eqn1 --> S1+S2 = array_sum
eqn2 -- > S1-S2 = diff
2*S1 = (array_sum + diff) we get the value of S1 and S2.
S1 = (array_sum+diff)/2 , S2 = (array_sum-S1)
both means S1 will always be even i.e. if we get a odd S1 value return "no such subset possible"

Code:------

class Solution{
public int count_the_number_of_subset_with_given_difference(int[] nums, int target){
int sum = 0;

    for(int x : nums)
        sum += x;
    
    if(((sum - target) % 2 == 1) || (target > sum))
        return 0;
    
    int n = nums.length;
    int s2 = (sum - target)/2;
    int[][] t = new int[n + 1][s2 + 1];
    t[0][0] = 1;
    
    for(int i = 1; i < n + 1; i++){
        for(int j = 0; j < s2 + 1; j++){
            if(nums[i - 1] <= j)
                t[i][j] = t[i-1][j] + t[i - 1][j - nums[i - 1]];
            else
                t[i][j] = t[i - 1][j];
        }
    }
    
    
    return t[n][s2];    
}

}

DO UPVOTE IT FOR MORE INTERVIEW VARIATION QUESTIONS :)

Comments (4)