Given an integer array, write a program to determine whether it can be divided into two subsets with equal sums.<\/p>\n
This problem is known as the ‘Subset Sum Problem’. It can be solved using Dynamic Programming.<\/p>\n
If it is possible to partition the subsets, print “YES”; otherwise, print “NO”.<\/p>\n
\n 4\n 1 5 11 5\n <\/pre>\nExample Output<\/h2>\n
\n YES\n <\/pre>\nApproach to Solve the Problem<\/h2>\n
To solve this problem, you should follow these steps:<\/p>\n
\n
- Calculate the sum of the input array.<\/li>\n
- If the sum is odd, it is impossible for the two subsets to have equal sums, so return “NO”.<\/li>\n
- If the sum is even, set the target value to half of the sum and use dynamic programming to determine if it can be achieved.<\/li>\n
- Set up a state table and check if each number can be used to form the target value.<\/li>\n<\/ol>\n
C++ Code<\/h2>\n
\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nbool canPartition(vector<int>& arr) {\n int sum = 0;\n for (int num : arr) sum += num;\n if (sum % 2 != 0) return false;\n\n int target = sum \/ 2;\n vector<bool> dp(target + 1, false);\n dp[0] = true;\n\n for (int num : arr) {\n for (int j = target; j >= num; j--) {\n dp[j] = dp[j] || dp[j - num];\n }\n }\n\n return dp[target];\n}\n\nint main() {\n int N;\n cin >> N;\n vector<int> arr(N);\n for (int i = 0; i < N; i++) {\n cin >> arr[i];\n }\n \n cout << (canPartition(arr) ? \"YES\" : \"NO\") << endl;\n return 0;\n}\n <\/pre>\nCode Explanation<\/h2>\n
The above code works as follows:<\/p>\n
\n
- First, it calculates the total sum of the number array.<\/li>\n
- It checks if the sum is odd. If it is odd, it returns “NO”.<\/li>\n
- If the sum is even, it sets the target value to half of the sum and initializes the dynamic programming array.<\/li>\n
- By iterating through each number, it checks if it can create the target value.<\/li>\n
- Ultimately, it prints “YES” if the target value can be created; otherwise, it prints “NO”.<\/li>\n<\/ol>\n
Time Complexity<\/h2>\n
The time complexity of this algorithm is O(N * target), where N is the number of input numbers and target is half of the total sum of the input array. This determines the number of operations that can be used to create different subsets.<\/p>\n
Conclusion<\/h2>\n
This concludes the code and explanation for the Subset Sum Problem. Such algorithmic problems often appear in coding tests, so it is good to practice them frequently. In the next lecture, we will cover more complex problems and their solutions.<\/p>\n
Questions and Feedback<\/h2>\n
If you have any questions about the code you wrote or any parts you find difficult to understand, feel free to leave a comment!<\/p>\n<\/div>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"