如何枚舉一個集合的所有k-組合？

Question

假設我有一個大小爲n的數值的有限集合。

問題：是否有一個有效的算法來枚舉該組的k組合，以便組合I在組合J之前如果I中元素的總和小於或等於J中元素的總和？

---

很明顯，可以簡單地枚舉組合並根據它們的總和進行排序。但是，如果該集合很大，所有組合的粗暴枚舉，更不用說排序了，將是不可行的。如果我只想獲得第一個選擇按總和排序的（n，k）組合，是否有可能在宇宙熱死之前獲得它們？

Answer 1

沒有用這種方法枚舉集合的多項式算法（除非P=NP）。

如果有這樣的算法（讓它成爲A），那麼我們就可以解決subset sum problem多項式：

1. 過程A
2. 做一個二進制搜索發現，總結最接近所需子集數。

請注意，步驟1運行多項式（假設），步驟2運行在O(log(2^n)) = O(n)。

結論：由於子集和問題是NP-Complete，有效地解決這一問題將被證明P = NP - 因此沒有已知的多項式解決問題的方法。

---

編輯：即使問題是NP難，讓「最小」 m子集可以在O(n+2^m)通過選擇最小m元素，生成所有這些m元素的子集做 - 並選擇那些最小的m。所以對於相當小的m值 - 計算它可能是可行的。