โปรแกรมตรวจสอบว่าเราสามารถแบ่งพาร์ติชั่นรายการด้วย k-partitions ผลรวมที่เท่ากันใน C++ . ได้หรือไม่

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k เราต้องตรวจสอบว่าเป็นไปได้หรือไม่ที่จะแบ่ง nums ออกเป็น k ชุดย่อยต่างๆ โดยที่ผลรวมของแต่ละชุดย่อยจะเท่ากัน

ดังนั้น หากอินพุตเป็น nums =[4, 2, 6, 5, 1, 6, 3] k =3 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถแบ่งพาร์ติชั่นได้ดังนี้ [6, 3], [6 , 2, 1], และ [4, 5].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน check() ซึ่งจะใช้อาร์เรย์ v
• สำหรับการเริ่มต้น i :=1 เมื่อ i <ขนาด v อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • ถ้า v[i] ไม่เท่ากับ v[0] แล้ว −
    • คืนค่าเท็จ
• คืนค่าจริง
• กำหนดฟังก์ชัน dfs() ซึ่งจะใช้ idx, หมายเลขอาร์เรย์, อุณหภูมิอาร์เรย์
• ถ้า idx เท่ากับขนาดของ nums แล้ว −
  • เช็คคืน(ชั่วคราว)
• ret :=false
• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ temp อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
  • temp[i] :=temp[i] + nums[idx]
  • ret :=dfs(idx + 1, nums, temp)
  • ถ้า ret เป็นจริง ดังนั้น −
    • คืนค่าจริง
  • temp[i] :=temp[i] - nums[idx]
• คืนค่าเท็จ
• จากวิธีหลัก ให้ทำดังนี้ -
• กำหนดอุณหภูมิอาร์เรย์ขนาด k
• คืนค่า dfs(0, nums, temp)

ตัวอย่าง (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);
      }
      bool ret = false;
      for (int i = 0; i < temp.size(); i++) {
         temp[i] += nums[idx];
         ret = dfs(idx + 1, nums, temp);
         if (ret)
            return true;
         temp[i] -= nums[idx];
      }
      return false;
   }
   bool solve(vector<int>& nums, int k) {
      vector<int> temp(k);
      return dfs(0, nums, temp);
   }
};
bool solve(vector<int>& nums, int k) {
   return (new Solution())->solve(nums, k);
}
int main(){
   vector<int> v = {4, 2, 6, 5, 1, 6, 3};
   int k = 3;
   cout << solve(v, 3);
}

อินพุต

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

ผลลัพธ์

1