Pembahagian dengan perbezaan yang diberikan

Memandangkan tatasusunan 'ARR', bahagikannya kepada dua subset (mungkin kosong) supaya penyatuan mereka ialah tatasusunan asal. Biarkan hasil tambah unsur dua subset ini ialah ‘S1’ dan ‘S2’.
Diberi perbezaan 'D', kira bilangan partition di mana 'S1' lebih besar daripada atau sama dengan 'S2' dan perbezaan antara 'S1' dan 'S2' adalah sama dengan 'D'. Memandangkan jawapannya mungkin terlalu besar, kembalikannya modulo ‘10^9 + 7’.
Jika 'Pi_Sj' menandakan Subset 'j' untuk Partition 'i'. Kemudian, dua partition P1 dan P2 dianggap berbeza jika:

Constraints :
1 ≤ T ≤ 10
1 ≤ N ≤ 50
0 ≤ D ≤ 2500
0 ≤ ARR[i] ≤ 50

Penyelesaian rekursif:
Ia akan membawa kepada TLE sebagai tidak optimum

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;

        return findSubsetSumCountEqualsToTarget(arr,n-1,(target-d)/2);

    }
    public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i]);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target);
        return (left+right)%mod;
    }

Penyelesaian Dp Memoization:

//create dp array in the driver class , and add dp to the function call
 int dp[][] = new int[n][(target-d)/2 +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);

public static int findSubsetSumCountEqualsToTarget(int [] arr, int i, int target,int dp[][]){

        if(i==0){
             //since 0<=arr[i]<=50; hence we have to check the possibility of 0 as well
            // if arr[i]==0 and target =0 then you should return 2 
            //as there are two solutions now ie either you will take this 0 or won't take this 0 
            //in either case of taking or not taking of 0 target will remain 0 only, as 0 won't alter target value hence there will be 2 possible solutions
            if(target ==0 && arr[i]==0) return 2; // extra line added to the usual appraoch because of presence of 0 in the array
            if(target==0 || arr[i]==target) return 1; // usual approach
            return 0;
        }
         if(dp[i][target]!=-1) return dp[i][target];
        int left =0;
        if(target>=arr[i]){
            left = findSubsetSumCountEqualsToTarget(arr,i-1,target-arr[i],dp);
        }
        int right = findSubsetSumCountEqualsToTarget(arr,i-1,target,dp);
        return dp[i][target] = (left+right)%mod;
    }
}

Penjadualan:

import java.util.*;
public class Solution {
    static int mod = (int)(1e9+7);
    public static int countPartitions(int n, int d, int[] arr) {
        // Write your code here.
        /*
        given : 
        1. s1 + s2 = sum; where sum is sum of all the elements in the array
        2. s1-s2 = D for s1>s2;

        modifications: 
        since s1+s2 = sum;hence s1 = sum-s2;
        from 2, 
        sum-s2-s2 = D;
        ie s2 = (sum-D)/2 = target;
        so we have to find all the subsets that are equal to target :)
        edge cases to avoid : 
        1. (sum-D)/2 can't be fraction value hence (sum-D) should be even 
        2. (sum-D)>=0 since it  can't be nagative as sum of all the elements of the array can't be negative
        */
        int target =0;
        for(int i : arr) target+=i;
        //implementing edge case first
        if(target-d<0 || (target-d)%2!=0) return 0;
       return findSolByTabulation(arr,n,(target-d)/2);
    }
    public static int findSolByTabulation(int [] arr, int n, int target){
         int dp[][] = new int[n][target +1] ;
        for(int row[]: dp) Arrays.fill(row,-1);
        if(arr[0] ==0) dp[0][0] = 2;
        else dp[0][0] = 1;
        if(arr[0]!=0 && arr[0]<=target) dp[0][arr[0]]=1;

        for(int i =1;i<arr.length;i++){
            for(int tar = 0;tar<=target;tar++){

                int left =0;
                if(tar>=arr[i]){
                    left = dp[i-1][tar-arr[i]];
                }
                int right = dp[i-1][tar];
                dp[i][tar] = (left+right);
            }

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

    }
}

Atas ialah kandungan terperinci Pembahagian dengan perbezaan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!