How to find all unique combinations of integers that add up to a target value?

[JakeT]

I'm trying to understand the mathematical approach behind generating all unique combinations of positive integers that sum to a given target.

For example:

• Target = 7
• Allowed numbers = [2, 3, 6, 7]

The valid combinations are:

[2, 2, 3]
[7]

My questions are:

1. Is there a standard mathematical method or formula to systematically generate such combinations?
2. How do we ensure that the combinations are unique (order doesn't matter)?
3. Does this relate to partitions or combinatorics in some way?
4. How can we generalize this for any target number and any list of integers?

I'm not looking for coding help — just the math reasoning or step-by-step logic behind solving this type of problem.

Thanks!

 

[BeachBanana]

I'm trying to understand the mathematical approach behind generating all unique combinations of positive integers that sum to a given target.

This is commonly known as the subset sum problem. You'll find many sources on the internet, e.g. Wikipedia, covering this topic.

 

[Steven G]

I would start with the largest number which is 7. Well that is 7 and that is one answer.
Now go to 6. You need to add 1 to 6 to get 7, but there is no 1. This means that 6 is not going to be part of a solution.
Now go to 3. You need to add 4 to 3 to get 7. The only way to get 4 is to use 2 and 2. So another answer is (2,2,3).
Now go to 2. You need to add 5 to 2 to get 7. The only way you can get 5 is by using 2 and 3. So another answer is (2,2,3), which of course has already been found.