Combinations ใน C++ - หาการจัดหมู่ทั้งหมด

สมมติว่าเรามีจำนวนเต็มสองจำนวน n และ k เราต้องหาการจัดหมู่ (combinations) ที่เป็นไปได้ทั้งหมดของ k ตัวเลขจาก 1 ... n ตัวอย่าง n = 4, k = 2 ผลลัพธ์คือ [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

ขั้นตอนการทำงาน (Recursive Backtracking)

1. ใช้ recursive function solve() รับ n, k, temp array, start เริ่มต้น start = 1
2. ถ้าขนาด temp array = k ใส่ temp ลง res array คืนค่า
3. วนลูป i := start ถึง n:
   • เพิ่ม i ลง temp
   • solve(n, k, temp, i + 1)
   • ลบองค์ประกอบสุดท้ายออกจาก temp
4. เรียก solve(n, k, [])
5. คืนค่า res

ตัวอย่างโค้ด (C++)

#include 
using namespace std;

void print_vector(vector> 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> res;
    void solve(int n, int k, vector temp, int start = 1){
        if(temp.size() == k){
            res.push_back(temp);
            return;
        }
        for(int i = start; i <= n; i++){
            temp.push_back(i);
            solve(n, k, temp, i + 1);
            temp.pop_back();
        }
    }
    vector> combine(int n, int k) {
        res.clear();
        vector temp;
        solve(n, k, temp);
        return res;
    }
};

int main(){
    Solution ob;
    print_vector(ob.combine(5, 3));
}

อินพุต

5 3

เอาต์พุต

[[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],[1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]]