Cho mảng A 4 phần tử, là số kẹo trong 4 túi. Phân chia 4 túi cho 2 bạn sao cho mỗi bạn nhận tổng kẹo bằng nhau. Trả về true/false.
Ví dụ
Với A = [1, 7, 11, 5], đầu ra True (1). Bạn 1 lấy túi 1 và 3 (1+11=12), bạn 2 lấy túi 2 và 4 (7+5=12).
Giải thuật
Với 4 túi, chỉ có các cách chia: (1+2 vs 3+4), (1+3 vs 2+4), (1+4 vs 2+3), (1+2+3 vs 4), (1+2+4 vs 3), (1+3+4 vs 2), (2+3+4 vs 1). Kiểm tra 7 trường hợp này.
Mã C++
#include <bits/stdc++.h>
using namespace std;
bool solve(vector<int> A) {
int a = A[0], b = A[1], c = A[2], d = A[3];
if (a + b == c + d || a + c == b + d || a + d == b + c ||
a + b + c == d || a + b + d == c || a + c + d == b || b + c + d == a)
return true;
else
return false;
}
int main() {
vector<int> A = { 1, 7, 11, 5 };
cout << solve(A) << endl;
}
Đầu vào / Đầu ra
Input: 1, 7, 11, 5
Output: 1