Partition problem is to determine whether a given set can be partitioned into two subsets such that the sum of elements in both subsets is the same.
The two partitions must have equal sum. Let say that sum is S , now the sum of the original set must be 2*S. so the sum is an even number. Taking this into consideration we can say that if the sum of the elements in the set is not even then there is no partition possible such that the sum of each partition is equal.
one more thing, if the sum of the element of the original set is K , then we just have to find a subset with the sum K/2.
Suppose we found the subset with sum K/2, then since the total sum is K , the elements not belonging to this subset will add up to K/2. Hence we found the two partitions.
All we need to do is to find the subset with sum K/2 (again K is the sum of the original set).
Notice how this problem turned out to be a variation of Subset-Sum-Problem.
I have already written a post about subset-sum-problem here, But still I want to write about here too.
Recusive approach:
so the problem now is to check if there's a subset with the sum K/2 , where K is the sum of the original set.
Imagine an empty subset in you mind. we have to pick the suitable element from the given set and place it in our imaginary subset.
The question is which element do we choose?
First thing, we cannot choose an element whose values if greater than the sum (K/2) . That will be violation, since we want our subset to have the sum (K/2). So when we find an element with value greater than K/2, we just skip it.
In other case where the value of the element is not greater than the sum, we will have choice whether to include this element in our subset or not. we then recursively solve both the case and take the case which results into our favour.
here's the solution in C++17:
The two partitions must have equal sum. Let say that sum is S , now the sum of the original set must be 2*S. so the sum is an even number. Taking this into consideration we can say that if the sum of the elements in the set is not even then there is no partition possible such that the sum of each partition is equal.
one more thing, if the sum of the element of the original set is K , then we just have to find a subset with the sum K/2.
Suppose we found the subset with sum K/2, then since the total sum is K , the elements not belonging to this subset will add up to K/2. Hence we found the two partitions.
All we need to do is to find the subset with sum K/2 (again K is the sum of the original set).
Notice how this problem turned out to be a variation of Subset-Sum-Problem.
I have already written a post about subset-sum-problem here, But still I want to write about here too.
Recusive approach:
so the problem now is to check if there's a subset with the sum K/2 , where K is the sum of the original set.
Imagine an empty subset in you mind. we have to pick the suitable element from the given set and place it in our imaginary subset.
The question is which element do we choose?
First thing, we cannot choose an element whose values if greater than the sum (K/2) . That will be violation, since we want our subset to have the sum (K/2). So when we find an element with value greater than K/2, we just skip it.
In other case where the value of the element is not greater than the sum, we will have choice whether to include this element in our subset or not. we then recursively solve both the case and take the case which results into our favour.
here's the solution in C++17:
No comments:
Post a Comment