砝码问题

coding>C++
1.1k 词

题目描述

小明童鞋有一个非常精确的天平和一堆砝码，数量为n$(1=<n<=20)$ 重量分别是$a_0, a_1,a_2,…,a_{n-1}$（都是正整数,且每一个重量不超过500）,他希望能把这些砝码都放在天平两端，并且天平恰好还是平衡的，显然一个一个的实验太麻烦了，有些情况下可能还没有解，所以就希望你帮忙写一个程序来判断有没有解。

输入

一个正整数n,代表砝码的个数

随后有n个整数  a0 a1 a2 …an-1 代表砝码的的重量

输出

如果可以做到输出”Of course,I can!”

不然输出””Sorry,I can’t!”

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>

using namespace std;
bool flag = false;

void count(int array[], int i, int n, int temp, int sum) {
    if (i > n)
        return;
    if (temp + array[i] == sum) {
        flag = true;
        return;
    }
    count(array, i + 1, n, temp + array[i], sum);
    count(array, i + 1, n, temp, sum);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    while (cin >> n) {
        int array[n];
        int sum = 0;
        flag = false;
        for (int i = 0; i < n; i++) {
            cin >> array[i];
            sum += array[i];
        }
        sort(array, array + n);
        if (sum % 2) {
            cout << "Sorry,I can't!" << endl;
            continue;
        }
        count(array, 0, n - 1, 0, sum / 2);
        if (flag)
            cout << "Of course,I can!" << endl;
        else
            cout << "Sorry,I can't!" << endl;
    }
    return 0;
}