# **UVa 10125 Sumsets**

今天解了一題UVa的題目
*UVa 10125 Sumsets*

## 題目敘述如下:

### **Description**
Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

### **Input**
Several S, each consisting of a line containing an integer 1 ≤ n ≤ 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and [phone] inclusive. The last line of input contains 0.

### **Output**
For each S, a single line containing d, or a single line containing "no solution".

| Sample Input | Sample Output |
| ------------------ | ------------- |
| 5 <br> 2 3 5 7 12 | 12 |
| 5 <br> 2 16 64 256 1024 |no solution|

## 解題心得
本題使用*set*這種stl，因為在set中資料會排序好。
接著，假設最大值是答案，找出剩下的資料中是否有三個值相加等於答案。這邊用三個for迴圈即可。

:::warning
本題用 *O(n^3^)* 的解法是可行的
:::

## 程式碼

#include <iostream>
#include <set>

#define no "no solution"

using namespace std;

int main()
{
    int s;
    set<int> gather;
    int d;
    while (1)
    {
        //輸入
        cin >> s;
        if (s == 0)
        {
            break;
            return 0;
        }
        int var;
        gather.clear();
        for (int i = 0; i < s; i++)
        {
            cin >> var;
            gather.insert(var);
        }
        int ans = 0;
        int a = 0, b = 0, c = 0;
        bool found = false;
        
        for (auto it1 = gather.rbegin(); it1 != gather.rend(); it1++)//找出最大值設為答案
        {
            d = *it1;
            for (auto it2 = gather.begin(); it2 != gather.end(); it2++)//找出第一個數字
            {
                if (*it2 == d) continue;
                for (auto it3 = next(it2); it3 != gather.end(); it3++)//找出第二個數字
                {
                    if (*it3 == d) continue;
                    for (auto it4 = next(it3); it4 != gather.end(); it4++)//找出第三個數字
                    {
                        if (*it4 == d) continue;
                        if (*it2 + *it3 + *it4 == d)判斷答案
                        {
                            ans = d;
                            found = true;
                            break;
                        }
                    }
                    if (found)
                    {
                        break;
                    }
                }
                if (found)
                {
                    break;
                }
            }
            if (found)
            {
                break;
            }
        }
        if (found)
        {
            cout << ans << endl;
        }
        else
        {
            cout << no << endl;
        }
    }
}

:::info
這邊我遇到一個小問題

if (found)
{
    break;
}

我一開始是利用ans != 0來判斷是否有找到答案

if (ans != 0)
{
    break;
}

但我沒想到的是，測資中會出現答案為0的狀況，導致我遇到了好幾個WA。
:::

本提到這邊結束~~