Chương trình kiểm tra xem chúng ta có thể phân vùng danh sách với k-phân vùng có tổng bằng nhau trong C ++ hay không

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải kiểm tra xem liệu có thể phân chia các num thành k tập con khác nhau mà tổng của mỗi tập con là như nhau hay không.

Vì vậy, nếu đầu vào giống như nums =[4, 2, 6, 5, 1, 6, 3] k =3, thì đầu ra sẽ là True, vì chúng ta có thể phân vùng chúng như:[6, 3], [6 , 2, 1] và [4, 5].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một kiểm tra hàm (), điều này sẽ lấy một mảng v,
• để khởi tạo i:=1, khi tôi
• nếu v [i] không bằng v [0], thì -
  • trả về false

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

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

Đầu ra

1