思路: 二进制枚举

用 $0$ 到 $2^{n}-1$ 这 $n$ 个数来表示选或不选，这样来构成一个子集。

这 $2^n$ 个数在二进制上可以看成是长度为 $n$ 的二进制位，那么第 $i$ 位为 $0$ 表示不选第 $i$ 个数，为 $1$ 表示选第 $i$ 个数。

如此就可以枚举 $0$ 到 $2^{n}-1$ ，然后再考虑每个数的每个二进制位，从而确定每个子集。

时间复杂度：$O(n\cdot 2^n)$

代码

C++

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    int ans = 0;
    int mask = 1 << n;
    for (int i = 0; i < mask; ++i) {
        long long sum = 0;
        int cnt = 0;
        for (int j = 0; j < n; ++j) {
            if (i >> j & 1) {
                sum += a[j];
                cnt += 1;
            }
        }
        if (sum >= 0) {
            ans += cnt;
        }
    }

    printf("%d\n", ans);
    return 0;
}

Python

n = int(input())

a = list(map(int, input().split()))

ans = 0
mask = 1 << n
i = 0
while i < mask:
    sum = 0
    cnt = 0
    j = 0
    while j < n:
        if i >> j & 1:
            sum += a[j]
            cnt += 1
        j += 1
    if sum >= 0:
        ans += cnt
    i += 1

print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; ++i)
            a[i] = scanner.nextInt();

        int ans = 0;
        int mask = 1 << n;
        for (int i = 0; i < mask; ++i) {
            long sum = 0;
            int cnt = 0;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    sum += a[j];
                    cnt += 1;
                }
            }
            if (sum >= 0) {
                ans += cnt;
            }
        }

        System.out.println(ans);
    }
}

题目描述

小红有一个长度为 $n$ 的数组。

对于一个数组，小红定义这个数组的数组权值为每个元素的元素权值之和。

对于数组中的第 $i$ 个元素，其元素权值为这个数组中，包含第 $i$ 个元素的所有子集中，所有元素之和大于等于 $0$ 的子集数量。

现在你需要输出小红的这个数组的数组权值。

输入描述

第一行，一个正整数 $n(1\leq n\leq 18)$ ，表示数组的长度。

第二行，$n$个整数表示数组 $a$ ，第 $i$ 个元素为 $a_i(-10^9 \leq a_i \leq 10^9)$

数据保证每个 $a_i$ 都是不同的。

输出描述

一个整数，表示小红这个数组的数组权值。

样例

输入

3
1 2 -3

输出

7

说明

$a[1]$ 的元素权值为 $3$ 。([1], [1, 2], [1, 2, -3])
$a[2]$ 的元素权值为 $3$ 。([2], [1, 2], [1, 2, -3])
$a[3]$ 的元素权值为 $1$ 。([1, 2, -3])

故数组权值之和为 3+3+1=7