주어진 차이가 있는 파티션

배열 'ARR'이 주어지면 해당 배열이 원래 배열이 되도록 두 개의 하위 집합(비어 있을 수도 있음)으로 분할합니다. 이 두 하위 집합의 요소의 합을 'S1'과 'S2'라고 합니다.
차이 'D'가 주어지면 'S1'이 'S2'보다 크거나 같고 'S1'과 'S2'의 차이가 'D'인 파티션의 수를 셉니다. 답이 너무 클 수 있으므로 '10^9 + 7' 모듈로 반환하세요.
'Pi_Sj'가 파티션 'i'에 대한 하위 집합 'j'를 나타내는 경우. 그런 다음 다음과 같은 경우 두 파티션 P1과 P2가 서로 다른 것으로 간주됩니다.

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

재귀적 솔루션:
최적화되지 않아 TLE로 이어질 것

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 메모 솔루션:

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

표:

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

    }
}

위 내용은 주어진 차이가 있는 파티션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!