मान लीजिए कि हमारे पास एक गैर-रिक्त सरणी है जिसमें केवल सकारात्मक संख्याएं हैं, हमें यह पता लगाना होगा कि क्या सरणी को दो सबसेट में विभाजित किया जा सकता है जैसे कि दोनों सबसेट में तत्वों का योग समान है। तो अगर इनपुट [1,5,11,5] जैसा है, तो आउटपुट सही होगा। चूंकि इस सरणी को [1, 5, 5] और [11]
. के रूप में विभाजित किया जा सकता हैइसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n :=सरणी का आकार
- योग :=0
- i के लिए:=0 से n - 1
- योग :=योग + अंक[i]
- यदि योग विषम है, तो झूठी वापसी करें
- योग :=योग/2
- साइज योग + 1 का डीपी नामक एक सरणी बनाएं
- dp[0] :=सच
- मैं के लिए 0 से n - 1 की सीमा में
- x :=nums[i]
- j के लिए:=j - x तक का योग
- dp[j] :=dp[j] या dp[j - x], जो 0 नहीं है
- रिटर्न डीपी[योग]
उदाहरण(C++)
एक बेहतर समझ प्राप्त करने के लिए आइए निम्नलिखित कार्यान्वयन को देखें -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
} इनपुट
[1,5,11,5]
आउटपुट
1