C++-এ কম্বিনেশন সম III (Combination Sum III)

kটি সংখ্যার সব সম্ভাব্য কম্বিনেশন বের করতে হবে যাদের যোগফল n হয়, শর্তে ১ থেকে ৯ পর্যন্ত সংখ্যাগুলোই ব্যবহার করা যাবে। প্রতিটি কম্বিনেশন অনন্য হবে এবং ডুপ্লিকেট কম্বিনেশন থাকবে না।

উদাহরণ

k = 3, n = 9 → আউটপুট: [[1,2,6], [1,3,5], [2,3,4]]

ব্যাকট্র্যাকিং সমাধান

রিকার্সিভভাবে সমাধান করুন:

• যদি n == 0 এবং টেম্প অ্যারের সাইজ == k হয়, তবে রেজাল্টে যোগ করুন
• start থেকে min(9, n) পর্যন্ত লুপ চালিয়ে প্রতিটি সংখ্যা ট্রাই করুন

C++ প্রোগ্রাম উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int>> 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;
    }
};

int main() {
    Solution ob;
    print_vector(ob.combinationSum3(2, 9));
    return 0;
}

ইনপুট / আউটপুট

Input: 3 9
Output: [[1, 8, ],[2, 7, ],[3, 6, ],[4, 5, ],]