मान लीजिए हमारे पास केवल धनात्मक संख्याओं वाली एक गैर-खाली सरणी है, हमें यह ढूंढना है कि क्या सरणी को दो उपसमुच्चयों (subsets) में विभाजित किया जा सकता है जैसे कि दोनों उपसमुच्चयों में तत्वों का योग समान हो। इसलिए यदि इनपुट [1,5,11,5] जैसा है, तो आउटपुट true होगा। क्योंकि इस सरणी को [1, 5, 5] और [11] के रूप में विभाजित किया जा सकता है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- n := सरणी का आकार
- sum := 0
- i := 0 से n - 1 तक
- sum := sum + nums[i]
- यदि sum विषम है, तो false लौटाएं
- sum := sum / 2
- sum + 1 आकार की एक सरणी dp बनाएं
- dp[0] := true
- i को 0 से n - 1 तक की रेंज में
- x := nums[i]
- j := sum से नीचे से j - x तक
- dp[j] := dp[j] या dp[j - x], जो 0 नहीं है
- dp[sum] लौटाएं
उदाहरण (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
