Combination Sum II - หาชุดที่ผลรวมเท่า Target (ไม่ซ้ำ) ใน C++

ภาพรวมปัญหา

มีชุดตัวเลข candidates (ไม่ซ้ำ) และ target หาชุดย่อย (combinations) ที่ผลรวมเท่า target แต่ละตัวเลือกได้สูงสุด 1 ครั้ง

ตัวอย่าง: [2,3,6,7,8], target=8 → [[2,6],[8]]

อัลกอริทึม (Backtracking + Sorting)

1. เรียงลำดับ candidates
2. ฟังก์ชัน solve(idx, a, b, temp):
   • ถ้า b==0: เพิ่ม temp เข้า res, return
   • ถ้า idx == size หรือ b < 0: return
   • for i = idx ถึง size-1:
     • ถ้า i > idx และ a[i] == a[i-1]: continue (ข้ามค่าซ้ำ)
     • temp.push_back(a[i])
     • solve(i+1, a, b-a[i], temp)
     • temp.pop_back()

ตัวอย่างโค้ด 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 idx, vector <int> &a, int b, vector <int> temp){
        if(b == 0){ res.push_back(temp); return; }
        if(idx == a.size()) return;
        if(b < 0) return;
        sort(a.begin(), a.end());
        for(int i = idx; i < a.size(); i++){
            if(i > idx && a[i] == a[i-1]) continue;
            temp.push_back(a[i]);
            solve(i + 1, a, b - a[i], temp);
            temp.pop_back();
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &a, int b){
        res.clear();
        vector <int> temp;
        solve(0, a, b, temp);
        return res;
    }
};

int main(){
    Solution ob;
    vector<int> v = {2,3,6,7,8};
    print_vector(ob.combinationSum2(v, 10));
}

Input / Output

Input:  [2,3,6,7,8] 8
Output: [[2, 8],[3, 7]]