Partition mit gegebener Differenz

Partitionieren Sie ein gegebenes Array „ARR“ in zwei Teilmengen (möglicherweise leer), sodass ihre Vereinigung das ursprüngliche Array ist. Die Summe der Elemente dieser beiden Teilmengen sei „S1“ und „S2“.
Zählen Sie bei einer gegebenen Differenz „D“ die Anzahl der Partitionen, in denen „S1“ größer oder gleich „S2“ ist und die Differenz zwischen „S1“ und „S2“ gleich „D“ ist. Da die Antwort möglicherweise zu groß ist, geben Sie sie modulo „10^9 + 7“ zurück.
Wenn „Pi_Sj“ die Teilmenge „j“ für Partition „i“ bezeichnet. Dann gelten zwei Partitionen P1 und P2 als unterschiedlich, wenn:

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

Rekursive Lösung:
Es wird zu TLE führen, da es nicht optimal ist

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;
    }

Dp Memoization-Lösung:

//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;
    }
}

Tabelle:

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];

    }
}

Das obige ist der detaillierte Inhalt vonPartition mit gegebener Differenz. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!