Combination Sum Calculator: Find All Combos

A combination sum calculator finds all unique sets of numbers from a given list that add up to a target sum, allowing repetition of each number as many times as you like. You enter the candidate numbers and the target, and it returns every distinct combination (order does not matter) whose sum equals the target. This is the classic “combination sum” problem from programming interviews and combinatorics.

Formula

The calculator uses a recursive backtracking algorithm. For a sorted list of candidate numbers nums and a target T, the function combos(i, remaining) explores two choices at each step: include the current number nums[i] (if it does not exceed the remaining sum) or skip it and move to the next index. The recurrence is:

combos(i, rem) = combos(i, rem – nums[i])  âˆª  combos(i+1, rem)

where i is the current index in the sorted list, rem is the remaining sum to reach the target, and the base cases are: if rem = 0, a valid combination is found; if rem < 0 or i ≥ length(nums), the branch stops. Each number can be used unlimited times because the first recursive call keeps the same index i.

Worked Example

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

1. Sort the list (already sorted): [2,3,6,7].
2. Start with i=0, rem=7.
3. Include 2 → rem=5. Include 2 again → rem=3. Include 2 again → rem=1 (too small, stop). Backtrack: include 3 → rem=0 → combination [2,2,3].
4. Backtrack to i=0, skip 2, take 3 → rem=4. Take 3 again → rem=1 (stop). Skip 3, take 6 → rem=1 (stop). Skip 6, take 7 → rem=0 → combination [7].
5. No other branches succeed.

Result: 2 combinations: [2,2,3] and [7]. The calculator displays the count (2) and the list.

When to Use This Calculator

Use it when you need to find all ways to make a specific total from a set of denominations or values, especially when repetition is allowed. Common real-world uses include:

• Finding coin change combinations (e.g., how many ways to make 50 cents from 1, 5, 10, 25-cent coins).
• Solving subset-sum puzzles where numbers can repeat.
• Generating possible sums for game scores or point combinations.
• Preparing for coding interviews that ask for the combination sum problem.

The calculator is purely mathematical; it does not consider currency limits, availability of items, or other constraints.

How to Read the Results

The output shows the total number of unique combinations and a list of them. Each combination is a set of numbers from your input that sums exactly to the target. Order does not matter: [2,2,3] is the same as [3,2,2] and appears only once. If the target is 0, the empty set is counted as one combination (a mathematical convention). If no combination exists, the count is 0 and the list is empty.

Common Mistakes and Limitations

• Order matters? This calculator treats combinations as unordered. If you need permutations (where order matters), the count will be higher.
• Duplicate numbers in input: If your list contains duplicates (e.g., [2,2,3]), the calculator may produce duplicate combinations. The standard problem assumes distinct candidates; remove duplicates first for accurate results.
• Negative numbers: The algorithm assumes all numbers are positive. Negative numbers can cause infinite loops because the sum may never increase.
• Large lists: The number of combinations can explode exponentially. For a list of 20 numbers, there can be millions of combinations, which may slow down the calculator.
• Zero in input: Including 0 leads to infinite recursion because you can add 0 forever without changing the sum. Remove 0 from the list.

Comparison with Related Problems

The combination sum problem is closely related to the subset sum problem (where each number can be used at most once) and the unbounded knapsack problem. The key difference is repetition: combination sum allows unlimited repetition, while subset sum does not. If you need each number only once, you would use a subset sum calculator or modify the algorithm to move to the next index after including a number. The count of combinations is also different from the number of permutations, which would be larger.

Frequently Asked Questions

Can I use negative numbers in the list? No. The algorithm assumes all numbers are positive. Negative numbers can cause infinite recursion because adding a negative number might keep the sum below the target forever. If you have negative numbers, you need a different approach (e.g., dynamic programming with bounded sums).

What if my target is 0? The empty combination (using no numbers) sums to 0, so the calculator returns 1 combination: an empty list. This is a standard convention in combinatorics.

Why does the calculator ignore the order of numbers? Because the problem asks for combinations, not permutations. The combination [2,3] and [3,2] are the same set, so only one is listed. If you need order to matter, multiply the count by the factorial of the number of elements in each combination, but that is a different problem.

How does the calculator handle duplicate numbers in my input? It treats each occurrence as a distinct item, which can produce duplicate combinations. For example, with nums=[2,2,3] and target=7, you might get [2,2,3] twice. To avoid this, remove duplicates from your input before using the calculator.

What is the time complexity? The worst-case time complexity is O(2^(T/min_num)), where T is the target and min_num is the smallest number in the list. In practice, it is much faster for small targets and lists, but can become slow for large inputs.

Related

• Bytes to MB Calculator: Convert Instantly
• Bytes to Gigabytes Calculator: Quick Conversion
• Bytes to MB Calculator: Convert Instantly

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