Introduction

Finding a group of numbers that adds up to a target is a classic search problem with several different versions. Sometimes you need any one valid group, sometimes all groups, and sometimes numbers can only be used once. The right algorithm depends on those rules, because brute force, backtracking, and dynamic programming solve different variants well.

Clarify the Problem Variant

Before choosing an algorithm, answer these questions:

• Do you need one valid group or all valid groups.
• Can each number be used once or many times.
• Are negative numbers allowed.
• Is input size small enough for exponential search.

Those details completely change the best solution. A subset-sum style problem with positive integers and one-use elements is very different from an unbounded combination problem.

Backtracking for One Valid Group

If the input is moderate in size and each number can be used at most once, backtracking is a practical starting point.

1def find_group(nums, target):
2    nums = sorted(nums)
3    path = []
4
5    def dfs(index, remaining):
6        if remaining == 0:
7            return path[:]
8        if remaining < 0:
9            return None
10
11        for i in range(index, len(nums)):
12            path.append(nums[i])
13            result = dfs(i + 1, remaining - nums[i])
14            if result is not None:
15                return result
16            path.pop()
17
18        return None
19
20    return dfs(0, target)
21
22
23print(find_group([3, 34, 4, 12, 5, 2], 9))

This returns one valid combination such as [4, 5].

Backtracking for All Unique Groups

If you need every valid combination, keep exploring instead of stopping at the first solution.

1def find_all_groups(nums, target):
2    nums = sorted(nums)
3    results = []
4    path = []
5
6    def dfs(index, remaining):
7        if remaining == 0:
8            results.append(path[:])
9            return
10        if remaining < 0:
11            return
12
13        prev = None
14        for i in range(index, len(nums)):
15            if nums[i] == prev:
16                continue
17            path.append(nums[i])
18            dfs(i + 1, remaining - nums[i])
19            path.pop()
20            prev = nums[i]
21
22    dfs(0, target)
23    return results
24
25
26print(find_all_groups([2, 3, 4, 5, 5], 10))

Sorting plus duplicate skipping prevents repeated equivalent results.

Dynamic Programming for Reachability

If you only need to know whether a target can be reached, dynamic programming is often more efficient than exploring every subset.

1def can_make_target(nums, target):
2    reachable = [False] * (target + 1)
3    reachable[0] = True
4
5    for num in nums:
6        for s in range(target, num - 1, -1):
7            if reachable[s - num]:
8                reachable[s] = True
9
10    return reachable[target]
11
12
13print(can_make_target([3, 34, 4, 12, 5, 2], 9))

This works well when numbers are non-negative and the target is not extremely large.

Recover an Actual Group With Dynamic Programming

You can extend DP to reconstruct one solution, not just a boolean answer.

1def find_group_dp(nums, target):
2    prev = {0: None}
3
4    for i, num in enumerate(nums):
5        updates = {}
6        for current_sum in list(prev.keys()):
7            next_sum = current_sum + num
8            if next_sum <= target and next_sum not in prev:
9                updates[next_sum] = (current_sum, i)
10        prev.update(updates)
11
12    if target not in prev:
13        return None
14
15    result = []
16    current = target
17    while current != 0:
18        previous_sum, index = prev[current]
19        result.append(nums[index])
20        current = previous_sum
21
22    result.reverse()
23    return result
24
25
26print(find_group_dp([3, 34, 4, 12, 5, 2], 9))

This is useful when the target is reasonably bounded and you need one concrete answer.

Complexity Tradeoffs

Backtracking can degrade to exponential time in the worst case, but it is flexible and easy to adapt when you need actual combinations. Dynamic programming can be much faster for moderate targets, but it depends on target size and usually assumes non-negative values.

Rule of thumb:

• small list, need full combinations: backtracking
• moderate target, need feasibility or one example: DP
• very large input or unrestricted negatives: first clarify whether the problem needs approximation or extra constraints

Pruning Makes a Big Difference

For positive sorted numbers, you can stop early once a value exceeds the remaining target.

That simple rule removes large parts of the search tree and often turns a slow brute force attempt into an acceptable solution for interview-size inputs.

Common Pitfalls

• Starting without defining whether numbers can be reused. Fix: write the exact problem contract first.
• Returning duplicate combinations when input contains repeated numbers. Fix: sort input and skip equal values at the same recursion depth.
• Using DP when the target is too large to store efficiently. Fix: check target size before choosing a table-based approach.
• Assuming negative numbers fit the same pruning logic. Fix: revisit the algorithm if negatives are allowed.
• Optimizing before deciding whether you need one group or all groups. Fix: choose the algorithm around the output requirement.

Summary

• Target-sum problems have multiple variants, not one universal algorithm.
• Backtracking is a good default when you need actual combinations.
• Dynamic programming is strong when target size is moderate and inputs are non-negative.
• Sorting and pruning can drastically improve search performance.
• Define reuse, duplicates, and output requirements before implementation.