โปรแกรมตรวจสอบการแบ่ง Partition เป็น k เซตผลรวมเท่ากันใน C++

ให้ nums และ k ตรวจสอบว่าแบ่ง nums เป็น k เซตที่ผลรวมเท่ากันได้หรือไม่

ตัวอย่าง: nums=[4,2,6,5,1,6,3], k=3 → True ([6,3],[6,2,1],[4,5] ผลรวม 9 ทุกคู่)

ขั้นตอนการแก้ปัญหา (Backtracking)

1. ฟังก์ชัน check(v): ตรวจสอบทุกค่าใน v เท่ากันหรือไม่
2. ฟังก์ชัน dfs(idx, nums, temp):
   • ถ้า idx == n: คืน check(temp)
   • ลองใส่ nums[idx] เข้า temp[i] ทุก i
   • ถ้า dfs(idx+1) true → คืน true
   • Backtrack: temp[i] -= nums[idx]
3. เริ่ม temp[k] = {0}, เรียก dfs(0, nums, temp)

หมายเหตุ: วิธีนี้เป็น Exponential อาจช้าสำหรับ n ใหญ่ ควรเพิ่ม Pruning (เช่น เรียง nums ใหญ่ไปเล็ก)

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

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

class Solution {
public:
    bool check(vector<int>& v) {
        for (int i = 1; i < v.size(); i++)
            if (v[i] != v[0]) return false;
        return true;
    }
    bool dfs(int idx, vector<int>& nums, vector<int>& temp) {
        if (idx == nums.size()) return check(temp);
        for (int i = 0; i < temp.size(); i++) {
            temp[i] += nums[idx];
            if (dfs(idx+1, nums, temp)) return true;
            temp[i] -= nums[idx];
        }
        return false;
    }
    bool solve(vector<int>& nums, int k) {
        vector<int> temp(k);
        return dfs(0, nums, temp);
    }
};

int main() {
    vector<int> v = {4,2,6,5,1,6,3};
    cout << (new Solution())->solve(v, 3); // 1 (true)
    return 0;
}

อินพุต

{4, 2, 6, 5, 1, 6, 3}, 3

เอาต์พุต

1