Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
We will be discussing 3 approaches for solving this problem
-
Recursion approach
// tc : o(2^n) as we have two choices take or not take at a given index of arr of size n
// space complexity : o(n) for stack space
// we have to find two subset where sum of both the subset is equal
// basically we have to find a subset where sum of all the elements of the subset is equals to the sum/2 where sum is total sum of all the elements in the array.
// This is because if one subset sum is sum/2, then there must be another subset whose sum is also sum/2 , hence sum/2 + sum/2 = sum of the array it self
// catch : if the sum of the array is odd then it can never be partitioned in two subset where sum of both the subset is same.
// hence the sum of the array has to be even
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums){
sum+=i;
}
if(sum%2!=0) return false;
int target = sum/2;
//now the problem has become very simple we have to find a subset whose sum is equals to target :)
// we will start from the lasat index;
return solve(nums,nums.length-1,target);
}
public boolean solve(int[] nums, int i, int target){
if(target == 0) return true;
if(i==0){
// if i ==0 it means we have to reached the last element or rather first element, now in order for it to return true the value at the index i should be target
if(nums[i] == target) return true;
else return false;
}
boolean take = false; // initially its false because inorder to take or consider the current index the value at that index should be less than or equals to the target else whats the point of even exploring it anyway.
if(nums[i]<=target){
take = solve(nums,i-1,target-nums[i]); // since we are taking current index into consideration hence the target will be reduced by nums[index]
}
//don't take
boolean dontTake = solve(nums,i-1,target);
return take || dontTake; // if any of them is true then we have found a subset where sum is equals to target
}
}
Enter fullscreen mode Exit fullscreen mode
-
Dp Memoization Approach: bottom up approach
// above sol is fine but it will lead to time limit exceeded issue
// Memoization top down approach
// there are two changing factors index and target hence we will be using 2d dp to solve
// this
//tc = two states O(n*m) n is sizse of arr, and m is different values of target while execution
// space c : o(n) + O(n*m) for auxillary stack space and dp array space
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums){
sum+=i;
}
if(sum%2!=0) return false;
int target = sum/2;
int dp[][] = new int[nums.length][target+1]; // as nums.length size will mean that index can range from 0 to nums.length-1 and target+1 size means that target value can range form 0 to target :)
for(int[] row: dp){
Arrays.fill(row,-1);
}
return solve(nums,nums.length-1,target,dp);
}
public boolean solve(int[] nums, int i, int target,int[][] dp){
if(target == 0) return true;
if(i==0){
if(nums[i] == target) return true;
else return false;
}
if(dp[i][target]!=-1) return dp[i][target]==1 ? true:false;
boolean take = false;
if(nums[i]<=target){
take = solve(nums,i-1,target-nums[i],dp);
}
boolean dontTake = solve(nums,i-1,target,dp);
dp[i][target] = (take || dontTake) ? 1 : 0;
if(dp[i][target] ==1) return true;
return false;
}
}
Enter fullscreen mode Exit fullscreen mode
-
Dp Tabulation Approach: top down approach
// tabulation approch for space optimization
// tc = O(n*m)
//space c : O(n*m); // since there are no auxillary stack space
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums){
sum+=i;
}
if(sum%2!=0) return false;
int target = sum/2;
int dp[][] = new int[nums.length][target+1]; // as nums.length size will mean that index can range from 0 to nums.length-1 and target+1 size means that target value can range form 0 to target :)
for(int[] row: dp){
Arrays.fill(row,-1);
}
//base case 1 if target is equals to 0 return true no matter what the index is
for(int i =0;i<nums.length;i++){
dp[i][0] = 1; // 1 is true, 0 is false and -1 is not traversed yet
}
// base case 2
//if the index is 0 and target value is equals to nums[index] return true
if(nums[0]<=target)
dp[0][nums[0]] = 1;
// now convert the states into for loop
//i =0 and target =0 state are already done hence move to i=1 to n-1 and target =1 to target
for(int i =1;i<nums.length;i++){
for(int tar =1;tar<=target;tar++){
// paste the recurrence relation from memoization solution as it is
boolean take = false;
if(nums[i]<=tar){
take = dp[i-1][tar-nums[i]]==1 ? true: false;
}
boolean dontTake = dp[i-1][tar] ==1 ? true:false;
dp[i][tar] = (take || dontTake) ? 1 : 0;
}
}
return dp[nums.length-1][target]==1 ? true : false;
}
}
Enter fullscreen mode Exit fullscreen mode
Dp Learnings (27 Part Series)
1 House Robber leetcode problem
2 Jump game leetcode problem
… 23 more parts…
3 Jump game II leetcode problem
4 Cherry Pickup II Leetcode Problem
5 Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
6 Maximum Sum Problem GeeksForGeeks
7 Count Palindrome Sub-Strings of a String GeeksForGeeks
8 Length of Longest Common Subsequence (LCS) and Longest common subsequence string leetcode
9 0/1 Knapsack Problem GeeksForGeeks both bounded and Unbounded
10 Shortest distance from source to all other nodes in a Directed Acyclic Graph
11 Coin change Leetcode
12 Coin Change 2 Leetcode
13 Target Sum or Partition with given difference Leetcode
14 Rod cutting Problem (similar to unbounded knapsack)
15 Length of longest common substring
16 Longest Palindromic subsequence (Same as Lcs)
17 Minimum Insertion steps needed to make a string palindrome (Same as LCS)
18 Minimum number of Insertion and deletion needed to convert String A to String B or make both the strings equal (same as lcs)
19 Shortest Common Super-sequence Leetcode (Same as Lcs string)
20 Distinct Subsequence Leetcode
21 Partition with given difference
22 Two best non overlapping events
23 Longest increasing subsequence
24 Edit distance
25 Maximum product subarray
26 Target sum
27 Maximum Multiplication Score
原文链接：Partition Equals Subset Sum Leetcode problem or Subset sum equals to target
暂无评论内容