Find All Sum Combinations (fasc) Algorithm(s) to find possible combinations to build a specific sum
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
This repo is archived. You can view files and clone it, but cannot push or open issues/pull-requests.
2tefan c05941964d Update 'README.md' 11 months ago
doc Add program 11 months ago
src/space/schober/algorithms/fasc Add program 11 months ago
.classpath Add program 11 months ago
.gitignore Initial commit 11 months ago
.project Add program 11 months ago
LICENSE Initial commit 11 months ago
README.md Update 'README.md' 11 months ago

README.md

FASC (Find All Sum Combinations)

Algorithm(s) to find possible combinations to build a specific sum.

How does it work?

A list of Items is used as an input file. Every item has a name and a cost. The algorithm tries to combine those items that they sum up to a specific sum. It works internally with a tree and recursive functions. Here is an example:

Input: [$x] A; [$y] B; [$z] C; [$w] D

The algorithm goes through every possible combination:

graph TD
    Start[start] --> A(A)
    Start[start] --> B(B)
    Start[start] --> C(C)
    Start[start] --> D(D)
    

    A --> AB(B)
    A --> AC(C)
    A --> AD(D)

    B --> BA(A)
    B --> BC(B)
    B --> BD(C)

    C --> CA(A)
    C --> CB(...)

    D --> DA(...)


    AB --> ABC(C)
    AB --> ABD(D)
    AC --> ACB(B)
    AC --> ACD(D)
    AD --> ADB(B)
    AD --> ADC(C)

    BA --> BAC(C)
    BA --> BAD(D)
    BC --> BCA(A)
    BC --> BCD(D)
    BD --> BDA(A)
    BD --> BDD(D)

    ABC --> ABCD(D)
    ABD --> ABCC(C)
    ACB --> ACBD(D)
    ACD --> ACDB(B)
    ADB --> ADBC(C)
    ADC --> ADCB(B)

    BAC(C) --> BACD(D)
    BAD(D) --> BADC(C)
    BCA(A) --> BCAD(D)
    BCD(D) --> BCDA(A)
    BDA(A) --> BDAD(D)
    BDD(D) --> BDDA(A)

If the sum equals the target sum, the combination is added to another List/Set. In the end, a LinkedList<LinkedList<Item>> or Set<LinkedList<Item>> with all possible combinations is returned. 🎉 To speed up the algorithm, if the sum exceeds the target sum, the branches will be skipped.

Use case

The reason I needed this algorithm was to find a combination to trade items in Rimworld with a specific amount of cash.