给定一个数组‘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中文网其他相关文章！
