Introduction

When people ask for the sum of numbers for all combinations, they may mean two different tasks. One task is to list every combination sum, and the other is to compute one final total that adds the sums of all combinations together. Clarifying that difference early avoids implementing an expensive algorithm when a closed-form result exists.

Core Sections

1. Clarify which combination model you need

The phrase "all combinations" is ambiguous. In practice, you usually need one of these models:

• All subsets of any size, including the empty subset.
• All subsets of a fixed size k.
• Ordered arrangements, which are permutations rather than combinations.

For subset-based tasks, order does not matter, so [1, 2] and [2, 1] are the same combination. For permutation-based tasks, they are different objects and counts grow much faster.

Also decide output shape:

• list of subset sums
• count of distinct subset sums
• total of all subset sums combined

Each output has a different best algorithm.

2. Enumerate subset sums when you need explicit values

If you need the actual list of sums, an iterative reachable-set update is a practical baseline. It is easy to validate and works for moderate input sizes.

1from typing import Iterable, List
2
3
4def all_subset_sums(nums: Iterable[int]) -> List[int]:
5    reachable = {0}
6    for n in nums:
7        reachable |= {s + n for s in reachable}
8    return sorted(reachable)
9
10
11print(all_subset_sums([1, 2, 3]))
12# [0, 1, 2, 3, 4, 5, 6]

This method returns distinct sums, not duplicate sums from different subsets. If you need duplicates preserved, use explicit subset generation with index tracking.

3. Compute total over all subset sums in linear time

If the goal is one aggregate number equal to the sum of every subset sum, there is a direct formula. In a list of length n, each element appears in exactly 2 raised to n - 1 subsets. Therefore:

total_all_subset_sums = sum(nums) * 2^(n - 1)

1def total_of_all_subset_sums(nums):
2    n = len(nums)
3    if n == 0:
4        return 0
5    return sum(nums) * (1 << (n - 1))
6
7
8print(total_of_all_subset_sums([1, 2, 3]))  # 24

This is much faster than enumeration and should be preferred whenever the requirement is aggregate total only.

4. Fixed-size combinations with dynamic programming

For fixed-size combinations, maintain a dynamic programming table where dp[c] stores reachable sums using exactly c elements. Update counts from high to low to avoid reusing the same element within one step.

1from collections import defaultdict
2
3
4def fixed_k_sums(nums, k):
5    dp = [set() for _ in range(k + 1)]
6    dp[0].add(0)
7    for n in nums:
8        for c in range(k, 0, -1):
9            for s in list(dp[c - 1]):
10                dp[c].add(s + n)
11    return sorted(dp[k])
12
13
14print(fixed_k_sums([1, 2, 3, 4], 2))
15# [3, 4, 5, 6, 7]

This pattern balances clarity and correctness for constrained-combination problems.

5. Complexity and practical limits

Even with dynamic programming, complexity grows with number of elements and sum range. For large inputs:

• prune impossible branches early
• apply bounds from domain rules
• separate negative and positive values carefully
• prefer aggregate formulas when possible

If values are very large or include many negatives, reachable-set growth can explode. In those cases, sampling or approximation may be better than exact enumeration.

6. Validation strategy

Use small lists where manual verification is easy, then compare optimized methods against brute force on random test cases.

A useful property check:

• 0 must always be present in subset sums for any input.
• maximum subset sum should equal sum of positive elements for unrestricted subsets.
• formula output should match brute force for small n.

These checks catch most logical mistakes before scaling up.

Common Pitfalls

• Not distinguishing between unique subset sums and sums with multiplicity.
• Enumerating all subsets when only the aggregate total is required.
• Confusing combinations and permutations, which changes counts dramatically.
• Updating dynamic programming states in the wrong direction and reusing elements incorrectly.
• Ignoring negative numbers, which can invalidate pruning assumptions.

Summary

• Start by defining exactly what "all combinations" means for your problem.
• Use reachable-set or dynamic programming methods when explicit sums are required.
• Use the linear-time contribution formula for the total over all subset sums.
• Add fixed-size dynamic programming when combination size is constrained.
• Validate optimized solutions against brute force on small inputs before production use.