Subset Sum

定义 Definition

“Subset sum（子集和）”指这样一个问题：给定一组整数和一个目标值，判断是否存在某个子集，其元素之和恰好等于目标值。它是计算机科学与算法中的经典问题（也常用于讲解 NP 完全性与动态规划）。

发音 Pronunciation (IPA)

/ˈsʌbˌsɛt sʌm/

例句 Examples

We used dynamic programming to solve a small subset sum instance.
我们用动态规划解决了一个较小规模的子集和实例。

The subset sum problem is often used to illustrate NP-completeness and the limits of efficient computation.
子集和问题常被用来说明 NP 完全性以及高效计算的局限。

词源 Etymology

该短语由 subset（子集） + sum（总和） 组成，字面意思就是“子集的和”。在算法与复杂性理论中，它被固定用作一个标准问题名称，用来研究“从集合中选一些数相加是否能得到目标值”。

相关词 Related Words

• Knapsack
• Dynamic Programming
• NP-Complete
• Reduction
• Complexity
• Decision Problem
• Optimization

文学与经典著作 Literary Works

• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：以子集和等问题作为 NP 完全性的代表性案例之一。
• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在讨论动态规划、伪多项式时间算法或相关章节时常提及子集和/背包类问题。
• The Art of Computer Programming（Donald E. Knuth）：在组合算法与相关讨论中涉及与“子集和”同类的子集选择与求和思想。