मान लीजिए हमें k संख्याओं के सभी संभावित संयोजन उत्पन्न करने हैं जो n संख्या तक जुड़ते हैं, यह देखते हुए कि केवल 1 से 9 तक की संख्याओं का उपयोग किया जा सकता है। प्रत्येक संयोजन संख्याओं का एक अद्वितीय सेट होना चाहिए। सभी संख्याएं धनात्मक होनी चाहिए, और समाधान में डुप्लिकेट संयोजन नहीं होने चाहिए। तो यदि k = 3 और n = 9, तो संभावित संयोजन [[1,2,6],[1,3,5],[2,3,4]] हैं
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- मान लीजिए हम solve नामक एक मेथड बनाकर इसे हल करेंगे। यह रिकर्सिव मेथड होगा, यह k, n, टेम्प ऐरे, और स्टार्ट लेगा। स्टार्ट प्रारंभ में 1 है
- यदि n = 0
- यदि टेम्प का आकार = k, तो टेम्प को res में डालें और लौटें
- i := स्टार्ट से 9 और n के न्यूनतम तक
- i को टेम्प में डालें
- solve(k, n – i, टेम्प, i + 1)
- टेम्प से अंतिम एलिमेंट हटाएं
- मुख्य मेथड इस तरह होगा
- टेम्प नामक एक खाली वेक्टर बनाएं
- solve(k, n, टेम्प)
- res लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
#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, ],]
