ZeroJudge B116: Plus and Minus

假設有 N 個正整數 A[1], A[2], …, A[N]，我們要在每一個數字之前加入 + 號或 – 號使得它們的總和為 0。

例如：1、2、3，我們可以得到 (-1) + (-2) + (+3) = 0；但是對於 2、2、1 則無法透過加入 + 號或 – 號使得它們的總和為 0。

請你寫一個程式來判斷任意 N 個正整數是否可以透過加入 + 號或 – 號使得它們的總和為 0。

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line of the input file contains two positive integers, M and N, separated by a space. M represents the number of test cases, and each test case contains N positive integers.
From the second line to the M+1th line, each line contains the specified N positive integers, separated by spaces. Here, 0 < M ≤ 10, and 0 < N ≤ 100.		對於每一組測試資料，若可以找到加入 + 號或 – 號使得它們的總和為 0 時，請輸出 Yes；否則請輸出 No。
4 3
1 2 3
3 2 1
2 2 2
5 1 6
2 8
1 2 3 4 5 6 7 8
12 12 10 11 34 22 33 26		Yes
Yes
No
Yes
Yes
Yes
ZeroJudge B116 Sample Test Case

Thought Process

This problem essentially requires finding two identical numbers. Therefore, if the total sum of the numbers is odd, you can directly output "No".

Using the DFS method to exhaustively add the numbers, if a combination of numbers sums to half of the total sum, it means that the remaining numbers will also sum to half of the total sum. Therefore, the goal is to find whether there is a combination that can sum to half of the total sum.

Sample Code－ZeroJudge B116: Plus and Minus

#include <iostream>
#include <vector>
using namespace std;

bool ok = false;
int sum = 0;

void DFS(vector<int>num, int index, int count) {
    if (ok || count > sum/2) return;
    if (count == sum/2) {
        ok = true;
        return;
    }
    if (index == num.size()) return;
    for (int i = index; i<num.size(); i++) {
        DFS(num, index+1, count+num[i]);
        if(ok) return;
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int M, N;
    while (cin >> M >> N) {
        for (int i = 0; i<M; i++) {
            vector<int>num;
            int max = -999999;
            sum = 0;
            for (int j = 0; j<N; j++) {
                int tmp;
                cin >> tmp;
                sum += tmp;
                if (tmp > max) max = tmp;
                num.push_back(tmp);
            }
            if (sum/2 < max || sum % 2 == 1) {
                cout << "No\n";
                continue;
            }
            ok = false;
            DFS(num, 0, 0);
            if (ok) {
                cout << "Yes\n";
                continue;
            }
            cout << "No\n";
        }
    }
}

//ZeroJudge B116
//Dr. SeanXD
Tags

Related Posts

Comments