窮舉法是一種藝術，例如下列集合\(\{1, 2, 3\}\)我們可以簡單地知道它的子集合數是\(8\)，分別為 \(\{1\}, \{2\} \{1, 2\}, \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\) 以及空集合\(\{\}\)。

對於一個程式碼而言，枚舉一個有\(n\)個數的集合的子集合的時間複雜度是\(O(2^n)\)，窮舉它們有很多方法，其中一個簡單的方法是用\(for\)迴圈從\(0\)跑到\(2^n-1\)，再將其二進制中的每個位元代表對應元素要取或不要取，即可枚舉出子集合。

拿集合\(\{1, 2, 3\}\)為例，\(3\)轉成二進制為\(011\)可以代表\(子集合_3\)沒有\(1\)，有\(2, 3\)

\(koukirocks\)遇到一個題目

輸入\(n\)個整數，請計算並輸出各種組合中，其合之最大值。每個元素可選取或不選取但不可重複選取。

輸入的數為\(C++\)中 \(int\) 不會溢位的數，\(1 \le n \le 40\)。

輸入說明

第一行為一個整數 \(n\) 第二行為 \(n\) 個可挑選的整數，同行數字以一個空白間隔。 輸入的數皆為 \(C++\) 中 \(int\) 不會溢位的數

輸出說明

輸出所有組合之和中的最大值 都不選取視為 \(0\)

範例輸入1

3
1 2 3

範例輸出1

6

範例說明1

範例中的組合分別為\( \{1\}, \{2\}, \{1, 2\}, \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} \)以及空集合 \(\{\}\)，其和分別為\(1, 2, 3, 3, 4, 5, 6\)，其中最大為\(6\)，故輸出\(6\)

子題配分