विचार करें कि हमें k संख्याओं के सभी संभावित संयोजनों को उत्पन्न करना है जो एक संख्या n तक जोड़ते हैं, यह देखते हुए कि केवल 1 से 9 तक की संख्याओं का उपयोग किया जा सकता है। प्रत्येक संयोजन संख्याओं का एक अद्वितीय समूह होना चाहिए। सभी संख्याएँ धनात्मक होनी चाहिए, और समाधान में डुप्लिकेट संयोजन नहीं होने चाहिए। तो अगर k =3 और n =9, तो संभावित संयोजन हैं [[1,2,6],[1,3,5],[2,3,4]]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- मान लीजिए कि हम इसे सॉल्व नामक एक विधि बनाकर हल करेंगे। यह पुनरावर्ती विधि होगी, इसमें k, n, अस्थायी सरणी और प्रारंभ होगा। प्रारंभ में 1 . है
- अगर n =0
- यदि अस्थायी का आकार =k है, तो अस्थायी को res में डालें और वापस लौटें
- i के लिए :=न्यूनतम 9 से प्रारंभ करें और n
- अस्थायी में i डालें
- समाधान (k, n - i, अस्थायी, i + 1)
- अस्थायी से अंतिम तत्व हटाएं
- मुख्य विधि इस प्रकार होगी
- अस्थायी नामक एक खाली वेक्टर बनाएं
- समाधान (के, एन, अस्थायी)
- रिटर्न रेस
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
vector < vector <int> > res;
void solve(int k, int n, vector <int> temp, int start = 1){
if(n == 0){
if(temp.size() == k){
res.push_back(temp);
}
return;
}
for(int i = start ; i <= min(9, n); i++){
temp.push_back(i);
solve(k, n - i, temp, i + 1);
temp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
res.clear();
vector <int> temp;
solve(k, n, temp);
return res;
}
};
main(){
Solution ob;
print_vector(ob.combinationSum3(2, 9));
} इनपुट
3 9
आउटपुट
[[1, 8, ],[2, 7, ],[3, 6, ],[4, 5, ],]
