algorithm - Anagram 生成器 - 这不是一种子集和吗？

Question

字谜:

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once;

子集和问题:

The problem is this: given a set of integers, is there a non-empty subset whose sum is zero?

For example, given the set { −7, −3, −2, 5, 8}, the answer is yes because the subset { −3, −2, 5} sums to zero. The problem is NP-complete.

现在假设我们有一个包含 n 个单词的字典。现在 Anagram Generation 问题可以表述为在字典中找到一组单词(n 个单词)，这些单词用完了输入的所有字母。那么它不就变成了一种子集和问题吗。

我错了吗？

Answer 1

两个问题类似但不是isomorphic .

• 在变位词中，字母的顺序很重要。在子集总和中，顺序无关紧要。
• 在变位词中，必须使用所有字母。在子集和中，任何子集都可以。
• 在一个变位词中，子组必须形成从一个相对较小的允许单词字典(字典)中提取的单词。在子集总和中，组不受限制(没有允许分组的字典)。