Enumerate all superincreasing subsequences

A sequence of positive real numbers S1, S2, S3, …, SN is called a superincreasing sequence if every element of the sequence is greater than the sum of all the previous elements in the sequence. E.g: 1, 3, 6, 13, 27, 52.

Given a sorted list A, I want to iterate over all combinations of A, which are superincreasing.

How example:

A = [28, 34, 44, 60, 71, 150, 167, 212, 230, 239, 415, 431, 434, 559, 688]

Valid examples of subsequences:

34, 44, 239, 434
34, 212, 434, 688


Here is a simple brute force example:

def is_superincreasing(seq):
total = 0
test = True
for n in seq:
if n <= total:
test = False
break
total += n
return test

def combinations(A):
N = len(A)
for i in range(2**N):
combo = []
for j in range(N):
if (i >> j) % 2 == 1:
combo.append(A[j])
if is_superincreasing(combo):
yield combo


I'd like to know if there is a better algorithm than O(2^n).

• 1. What's a "superincreasing combination of A"? 2. What is your question? What approaches have you already considered? Please edit the question to clarify.
– D.W.
Aug 17, 2022 at 21:42
• @D.W., thanks! I've updated the question. Aug 17, 2022 at 22:30
• What is a "combination of A"? Do you mean "subsequence"?
– D.W.
Aug 17, 2022 at 23:12
• cs.stackexchange.com/tags/dynamic-programming/info
– D.W.
Aug 18, 2022 at 0:29
• Also, note that if $A = \{1,2,4,8,...,2^k,...,2^n\}$ you can't do better than $\Omega(2^n)$. However, like @D.W. says, I believe that dynamic programming and memoization will give you optimal results. Aug 18, 2022 at 13:59

May not be the best solution in terms of complexity, because of duplicate summation operations with further elements, but much better in the general case.

def superincreasing_combinations(g):
ln = len(g) - 1
operate = {}
ret = set()

for i, e in enumerate(g):
operate[(e,)] = (i, e)

while operate:
o, v = operate.popitem()
last_index, sumo = v

while last_index < ln:
last_index += 1
next = g[last_index]
if next > sumo:
operate[(*o, next)] = (last_index, sumo + next)