数字组合

题目描述

有 $n$ 个正整数 $a_1,\dots,a_n$ 和一个目标值 $t$ （ $1 \leqslant n \leqslant 20$ ， $1 \leqslant t \leqslant 1000$ ），求选出若干个数使和恰为 $t$ 的组合方式数——只看选了哪些下标，选取顺序不产生新方案（ $1+4$ 与 $4+1$ 是同一组合）。输入第一行是 $n$ 和 $t$ ，第二行是 $n$ 个正整数；输出组合方式的数目。样例： $n=5$ 、 $t=5$ 、 $a=(1,2,3,4,5)$ ，答案为 $3$ ，对应 $1+4$ 、 $2+3$ 、 $5$ 。

思路

设 ways[s] 为从已考虑的数中选出若干、和恰为 $s$ 的组合数，ways[0]=1 表示一个数都不选。每个数至多用一次，于是这是 0/1 背包的方案计数版：对每个 $a_i$ 做 ways[s] += ways[s-a[i]]，容量必须从 $t$ 倒序枚举，右侧读到的才是本轮更新前的旧值（读新值就变成完全背包，会重复使用同一个数）。答案为 ways[t]，复杂度 $O(nt)$ 。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:41
# update_at: 2026-09-30 03:41

import sys
from itertools import islice


def count_subsets(values: list[int], target: int) -> int:
    """选出若干个数使和恰为 target 的组合数（选哪几个数，不计选取顺序）。

    ways[s] 是「已处理的那批数里，和恰为 s 的组合数」。每个数只允许用一次，
    所以每轮更新必须写成同时取旧值的 new = old + 错位后的 old：切片右侧在赋值前
    已全部求值，zip 读到的旧 ways 不会混入本轮刚写的结果（等价于倒序枚举）。
    """
    ways = [1] + [0] * target  # ways[0] = 1：一个数都不选，和恰为 0
    for value in values:
        ways[value:] = [take + skip for take, skip in zip(ways[value:], ways)]
    return ways[target]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    count, target = next(data), next(data)          # 题面的 n 与 t
    values = list(islice(data, count))
    print(count_subsets(values, target))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 08:09
 * update_at: 2026-10-05 08:09
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXT = 1005;

int n;      // 正整数的个数
int t;      // 目标组合和
int a[25];  // 输入的 n 个正整数

ll ways[MAXT]; // ways[s] = 从已考虑的数中选出若干、和恰为 s 的组合数

int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // ways[0] = 1：一个数都不选时和恰好为 0，方案数为 1
    ways[0] = 1;
    for (int i = 1; i <= n; i++) {
        // 每个数至多用一次，所以容量必须倒序枚举，读到的是上一轮的旧值
        for (int s = t; s >= a[i]; s--) {
            ways[s] += ways[s - a[i]];
        }
    }

    cout << ways[t] << endl;
    return 0;
}

目录

题目描述

思路

参考代码