Find all combinations that add up to a given number

Grasshopper
1

Hello,

I am lost with this one. Let’s say i have a given sum of 5 and 3 integers I can use to add up (1,2,3). How do I find all combinations using grasshopper?

1,1,1,1,1
1,1,1,2
1,1,3
2,2,1
3,2

2

This is called a knapsack problem.

Do you mind if I ask why you’re trying to do this in Grasshopper? I’m imagining some comp sci professor laughing as he gives an assignment like this: Grasshopper is great; it’s just not a language you’d typically use for a problem like this.

However, once you know what it is (knapsack problem), it’s been discussed:
Reach a variable number with the sum of fixed numbers - Grasshopper Developer - McNeel Forum

and you could google search
site:discourse.mcneel.com grasshopper “knapsack” problem

3

Thanks for reply.

I need it to divide same, rectangular surfaces using given elements.

Knapsack problem is not exactly what I am looking for as there is only one answer - the one using biggest numbers possible while I am looking for all combinations (unless I misunderstood)

4

Yes: I think the simplest way to get what you want is to take a brute force (check all combinations) solver for the knapsack problem and modify it to spit out all sum matches instead of spitting out the first and stopping or outputting only the ‘best’.

I think that one of the C# component approaches should provide the core that you need in that regard?

5

Hi,
There you go, you can adapt it to your use case

def find_combinations(target, current_sum, start, numbers, current_combination, result):
    if current_sum == target:
        result.append(current_combination[:])
        return
    for i in range(start, len(numbers)):
        if current_sum + numbers[i] > target:
            break  
        current_combination.append(numbers[i])
        find_combinations(target, current_sum + numbers[i], i, numbers, current_combination, result)
        current_combination.pop()
def main():
    try:
        target_sum = int(input("Enter the target sum: "))
        if target_sum <= 0:
            raise ValueError
    except ValueError:
        print("Please enter a valid positive integer.")
        return
    numbers = list(range(1, target_sum))
    result = []
    find_combinations(target_sum, 0, 0, numbers, [], result)
    for comb in result:
        print(comb)
main()
6

Combos_2023Dec12a
Combos_2023Dec12a882×579 47.4 KB

Combos_2023Dec12a.gh (14.2 KB)

Python:

__author__ = "Joseph Oster"
__version__ = "2021.01.15"

from itertools import combinations  

combos = []
for i in range(2,len(vals)+1):
    comb = combinations(vals, i)
    for c in list(comb): 
        combos.append("+".join(c))

C = combos

Based on this: