Combination Sum Calculator: Find All Combos

This calculator finds all unique combinations of numbers from a given list that add up to a target sum. You enter the list of candidate numbers and the target value, and it returns every combination (without repetition of the same index) that sums exactly to the target. The result is shown as a list of combinations, along with the total count.

Formula

The calculator uses a recursive backtracking algorithm. The core idea is: for a given target T and a list of numbers nums, you try each number n in order. If n equals T, you record a combination. If n is less than T, you recursively try to find combinations that sum to T – n using the remaining numbers (those after n in the list, to avoid duplicates). If n is greater than T, skip it.

In symbols, the set of combinations C(T, i) starting from index i is:

C(T, i) = { [nums[i]] + c : c ∈ C(T – nums[i], i+1) } ∪ C(T, i+1)

where each combination is a list of numbers, and the base cases are: if T = 0, return an empty list (success); if T < 0 or i ≥ length of nums, return nothing (failure).

Worked Example

Using the default values: nums = [2, 3, 6, 7], target = 7.

1. Start with target 7, index 0 (number 2). 2 < 7, so recurse with target 5, index 1.
2. At target 5, index 1 (number 3). 3 < 5, so recurse with target 2, index 2.
3. At target 2, index 2 (number 6). 6 > 2, skip. Index 3 (number 7). 7 > 2, skip. End of list, no combination.
4. Back to target 5, index 2 (number 6). 6 > 5, skip. Index 3 (number 7). 7 > 5, skip. No combination.
5. Back to target 5, index 1 (number 3) done. Move to index 2 (number 6). 6 > 5, skip. Index 3 (number 7). 7 > 5, skip. No combination from target 5.
6. Back to target 7, index 0 (number 2) done. Move to index 1 (number 3). 3 < 7, recurse with target 4, index 2.
7. At target 4, index 2 (number 6). 6 > 4, skip. Index 3 (number 7). 7 > 4, skip. No combination.
8. Back to target 7, index 1 (number 3) done. Move to index 2 (number 6). 6 < 7, recurse with target 1, index 3.
9. At target 1, index 3 (number 7). 7 > 1, skip. No combination.
10. Back to target 7, index 2 (number 6) done. Move to index 3 (number 7). 7 equals 7, record [7].

The combinations found are [2, 3, 6? no – wait, check step 2-4: no, that failed. Actually [2,3] sums to 5, not 7. Let me re-trace correctly: the algorithm finds [7] and also [2,?] – let’s see: from step 1, target 5, index 1 (3) – 3 < 5, recurse target 2, index 2 – no. Then index 2 (6) – 6 > 5, skip. So no [2,?]. But what about [2,2,3]? Not allowed because each index used once. So only [7] and also [2,?] – wait, what about [2,5]? No 5 in list. So the only combination is [7]. But the classic problem allows reuse of the same number? No, this calculator does not allow reuse – it uses each index once. So the result is [[7]] with count 1.

Let me re-check with the default: the calculator returns [[7]] and count 1. That matches the algorithm above.

When to Use This Calculator

• Solving the “Combination Sumâ€� coding interview problem (LeetCode 39 or 40, depending on reuse rules).
• Finding which items from a price list exactly match a budget (e.g., which products total $50).
• Checking if a set of weights can combine to a target weight.
• Generating all possible subsets that meet a sum condition for small lists.

How to Read the Result

The output lists each combination as a set of numbers in the order they appear in the input list. The count shows how many distinct combinations exist. If the count is 0, no combination sums to the target. Note that the order of numbers within a combination is fixed (sorted by input order), and two combinations are considered the same if they contain the same numbers, regardless of order.

Common Mistakes and Limitations

• Duplicate numbers in input: If your list contains duplicate values, the calculator will treat them as separate items (different indices), so you may get duplicate combinations. For example, [2,2] with target 4 gives one combination [2,2] (using both indices), but [2,2,2] with target 4 gives three identical-looking [2,2] combinations because any two of the three 2s work. To avoid this, remove duplicates before entering.
• Negative numbers: The algorithm assumes all numbers are non-negative. If you include negative numbers, it may still work but can produce infinite loops in some implementations; this calculator restricts to non-negative.
• Large lists: The number of combinations grows exponentially. For lists longer than about 20-25 numbers, the calculator may become slow or run out of memory. Stick to small lists for practical use.
• Target too large: If the target is larger than the sum of all numbers, the result will be 0 combinations. The calculator handles this gracefully.

Comparison: With vs. Without Reuse

The classic “Combination Sum� problem (LeetCode 39) allows reusing the same number multiple times. This calculator does not allow reuse – each index can be used at most once. That matches LeetCode 40 (Combination Sum II) when the input has duplicates, but without the duplicate-removal step. If you need reuse, you would modify the recursion to allow the same index again (i.e., recurse with the same index instead of i+1). For example, with nums=[2,3,6,7] and target=7, allowing reuse gives [2,2,3] and [7] – two combinations. This calculator gives only [7] because 2+2+3 requires reusing 2.

Frequently Asked Questions

How do I enter a list of numbers?

Type the numbers separated by commas, like “2,3,6,7�. Spaces are optional. Do not use brackets or other characters.

What if my target is 0?

If the target is 0, the only valid combination is the empty set, but since we don’t display empty sets, the result will show 0 combinations. In mathematical terms, there is exactly one way to sum to 0 (using no numbers), but this calculator omits it for clarity.

Can I use decimal numbers?

Yes, you can enter decimals like “1.5, 2.5�. The algorithm works with any non-negative real numbers. However, be aware of floating-point rounding errors – e.g., 0.1 + 0.2 may not equal 0.3 exactly. If you need exactness, use integers or multiply everything by a power of 10.

Why does the calculator give fewer combinations than I expected?

Most likely because you expected to allow reusing numbers, or because you have duplicate numbers in your list. Check the input for duplicates and decide whether reuse is intended. If you need reuse, this calculator won’t do it – you’ll need a different tool.

How many combinations can this calculator handle?

There’s no hard limit, but performance degrades with list length. For a list of 20 numbers, the worst-case number of subsets is 2^20 = 1,048,576, which is too many to display. In practice, keep the list under 15-20 numbers and the target reasonably small.

Does the order of numbers in the input matter?

Yes, because combinations are generated based on index order. If you reorder the input, the combinations will be listed in a different order, but the set of combinations will be the same (as long as you don’t have duplicates). For example, [2,3] and [3,2] both sum to 5, but only one will appear depending on input order.

Related

• Calculate Image Magnification With a Simple Formula
• Heat of Combustion: Formula and Calculation
• Enthalpy of Combustion: Formula and Calculation

in nums | Numbers (comma-separated) | - | 2,3,6,7 | 0
in target | Target sum | - | 7 | 0
out combos | Combinations | - | combos(nums,target) | 0
out count | Number of combinations | - | count(combos(nums,target)) | 0