Introduction

If each of n numbers can be used with either a plus sign or a minus sign, then there are 2^n possible sign assignments. The programming task is usually to generate every resulting sum, or to count how many ways a target sum can be formed.

Model the problem as sign choices

For each value, you have exactly two options:

• add it
• subtract it

So for values [1, 2, 3], the possible expressions include:

• '+1 +2 +3'
• '+1 +2 -3'
• '+1 -2 +3'
• '+1 -2 -3'
• '-1 +2 +3'
• '-1 +2 -3'
• '-1 -2 +3'
• '-1 -2 -3'

That gives 2^3 = 8 possibilities.

Recursive generation is the clearest solution

At each step, choose a sign for the current value and recurse to the next index.

1def all_signed_sums(values):
2    result = []
3
4    def backtrack(index, total):
5        if index == len(values):
6            result.append(total)
7            return
8
9        backtrack(index + 1, total + values[index])
10        backtrack(index + 1, total - values[index])
11
12    backtrack(0, 0)
13    return result
14
15
16values = [1, 2, 3]
17print(all_signed_sums(values))

This produces every sum, including duplicates. Duplicates are normal because different sign assignments can lead to the same numeric result.

Generate the actual expressions too

If you want to show the expressions rather than only the totals, store the chosen signs during recursion.

1def signed_expressions(values):
2    result = []
3
4    def backtrack(index, total, pieces):
5        if index == len(values):
6            result.append((" ".join(pieces), total))
7            return
8
9        value = values[index]
10
11        backtrack(index + 1, total + value, pieces + [f"+{value}"])
12        backtrack(index + 1, total - value, pieces + [f"-{value}"])
13
14    backtrack(0, 0, [])
15    return result
16
17
18for expr, total in signed_expressions([1, 2, 3]):
19    print(f"{expr} = {total}")

This is useful for debugging, teaching, or tools where you need to inspect how the sum was built.

Bitmask iteration is another option

You can also treat each sign choice as one bit in a mask. Bit 1 might mean plus and bit 0 might mean minus.

1def all_signed_sums_bitmask(values):
2    result = []
3    n = len(values)
4
5    for mask in range(1 << n):
6        total = 0
7        for i, value in enumerate(values):
8            if mask & (1 << i):
9                total += value
10            else:
11                total -= value
12        result.append(total)
13
14    return result
15
16
17print(all_signed_sums_bitmask([1, 2, 3]))

This is iterative and compact, though the recursive version is often easier to adapt.

Complexity and what it implies

The number of possibilities doubles for every extra value, so runtime is inherently exponential. If the requirement is to list all results, there is no way around that growth.

For example:

• 'n = 10 gives 1024 sign assignments'
• 'n = 20 gives 1,048,576'

That is why you should be careful with large inputs. Often the real task is not to enumerate everything, but to answer a more focused question such as whether a target sum is reachable.

Counting ways to hit a target

If the real goal is "how many sign assignments produce sum T," dynamic programming can be better than listing all expressions.

1from collections import Counter
2
3def count_target_ways(values, target):
4    counts = Counter({0: 1})
5
6    for value in values:
7        next_counts = Counter()
8        for total, ways in counts.items():
9            next_counts[total + value] += ways
10            next_counts[total - value] += ways
11        counts = next_counts
12
13    return counts[target]
14
15
16print(count_target_ways([1, 2, 3], 0))

This still reflects the same plus-or-minus structure, but it avoids storing every individual expression separately.

Common Pitfalls

The biggest mistake is forgetting that different sign assignments can lead to the same final sum. If you need unique totals only, put the results in a set instead of a list.

Another issue is underestimating the exponential growth. Generating every expression works for small n, but it becomes expensive quickly.

Developers also sometimes start recursion with the first value already added and forget the branch where it is subtracted. Starting from index 0 and total 0 keeps the logic symmetric and less error-prone.

Finally, check whether you actually need all sums. If the real question is about a target, counting or reachability algorithms are often more practical.

Summary

• Each number has two sign choices, so there are 2^n possible expressions.
• Recursive backtracking is the clearest way to generate every sum.
• Bitmask iteration is a compact iterative alternative.
• Duplicate sums are normal because different sign assignments can collide numerically.
• If you only need target counts or reachability, dynamic programming may be better than full enumeration.