3
$\begingroup$

If I have a list of $38$ numbers (from $1$ to $40$, excluding numbers $3$ and $12$), how can I find all the combinations of $4$ different numbers from that list that will give me a total of $68$ when they are added together? Is there a mathematical formula that can be used here?

Places I have looked for an answer:

Finding all combinations that sum to a target

Finding all combinations of four numbers that equal a sum in R

I feel I'm close to answer with the above link but I am having some difficulties understanding the process to tweak the answers mentioned therein to fit my problem.

Additional note: The four numbers must be unique in each combination. That is, a number cannot be used twice or more in the same combination.

$\endgroup$
4
  • $\begingroup$ The smallest of the four numbers cannot be larger than $15$, because of $16+17+18+19 = 70$. You could set the smallest number to $1, 2, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15$ and analyze the combinations for the remaining three numbers accordingly. $\endgroup$ Mar 17, 2018 at 20:19
  • 1
    $\begingroup$ yes, stars and bars with some exclusions. $\endgroup$
    – Abr001am
    Mar 18, 2018 at 0:08
  • 1
    $\begingroup$ @MikeMathMan you need to handle stars/bars cautiously by using exclusion/inclusion principle, this regards duplicates too moreover 3 and 12 $\endgroup$
    – Abr001am
    Mar 18, 2018 at 0:23
  • 1
    $\begingroup$ @MikeMathMan see here an approximately similar question and its solution. $\endgroup$
    – Abr001am
    Mar 18, 2018 at 3:10

2 Answers 2

0
$\begingroup$

Once you remove the two numbers $3$ and $12$, the chance of finding any 'nice math formula(s)' to solve the problem most likely plummet.

You said you were attempting to tweak some $\text{R programming language}$ code. But consider this brute force method (I am learning Python):

#--------*---------*---------*---------*---------*---------*---------*---------*
# Desc: Sum 4 addendums up to 68
#--------*---------*---------*---------*---------*---------*---------*---------*
import sys, itertools

while True:
#                                  # create U = [1, 2, ..., 40] 
    U = list(range(1, 41))
#                                  # remove 12 from U
    U.pop(11)
#                                  # remove 3  from U    
    U.pop(2)
    countEmUp = 0
    countRejects = 0
    for i in itertools.product(U, U, U, U):
#                                  # to screen for uniqueness,
#                                  # consider standard form  
        if i[0] < i[1] and i[1] < i[2] and i[2] < i[3]:
            pass
        else:
            countRejects = countRejects + 1
            continue
        if i[0] + i[1] + i[2] + i[3] == 68:
            countEmUp = countEmUp + 1
#                                  # print first 10 4-tuples
#                                  # that add up to 68
            if countEmUp <= 10:
                print(i)
        else:
            countRejects = countRejects + 1    
    print('Combinations Adding to Sixty-Eight =     ', countEmUp)
    print('Rejected tuples                    = ', countRejects)
    print('                                     ', '-------')
    print('38 raised to the fourth power      = ', 38*38*38*38)
    sys.exit()

OUTPUT:

(1, 2, 25, 40)
(1, 2, 26, 39)
(1, 2, 27, 38)
(1, 2, 28, 37)
(1, 2, 29, 36)
(1, 2, 30, 35)
(1, 2, 31, 34)
(1, 2, 32, 33)
(1, 4, 23, 40)
(1, 4, 24, 39)
Combinations Adding to Sixty-Eight =      996
Rejected tuples                    =  2084140
                                      -------
38 raised to the fourth power      =  2085136
$\endgroup$
0
0
$\begingroup$

I have written my solution in C++ but it should be fairly straightforward to convert it to some other language.

My short answer is that there are 996 solutions.

The solution in the code below finds ALL solutions (if they exist). Meaning that you will find solutions for 1 sum, 2 sums, 3 sums, 4 sums...., n sums. It is assumed that the array that is passed to find_Ksum is sorted in ascending order. In the end, I just loop through all solutions and check how many are 4-sums, and print them out. Note that you might want to add the verbose printing in find_Ksum when debugging.

You can use this solution and optimize it for the specific case of a 4-sum, which I would do if I was in a coding interview. But since this method is a bit more general you might want to have it as a backup solution to see that you don't miss any cases when you specialize.

Since I don't know how the exact problem formulation I want to mention that assuming that the solution is order dependent you need to permute all solutions as well since you have unique entries in the list. That will end up in 996 * 4! = 23904 solutions.

The solution is recursive and uses backtracking to find all:

int find_lower_pos(int val, int i0, const std::vector<int>& vals)
{
    // uses interval halving to find the solution
    int left = i0;
    int right = vals.size() - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        int v = vals[mid];
        if (v == val)
            return mid;
        else if (v > val)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return left;
}

void find_Ksum(int K, int i0, int i1, const std::vector<int>& vals, std::vector<int> cur, std::vector<std::vector<int>> solutions)
{
    int v0 = vals[i0];
    int remainder = K - v0;
    if (i0 > i1 || remainder < 0) // no solution
        return;
    cur.push_back(v0);

    if (remainder == 0) // this is a solution.... terminate
    {
        // The lines below prints all solutions explicitly
        /*std::cout << "Solution: ";
        for (auto v : cur)
            std::cout << v << ", ";
        std::cout << "\n";*/
        // replace the two lines with the third to only consider 4-sums
        //if (cur.size() == 4)
        //    solutions.push_back(cur);
        solutions.push_back(cur);
        return;
    }

    // optimization: uncomment to constrain solutions to only have 4-sums
    //if (cur.size() >= 4)
    //    return;

    // optimization: constrain i1 to avoid searching more than necessary
    if (vals[i1] > remainder)
        i1 = find_lower_pos(remainder, i0, vals);

    for(int i = i0+1; i <= i1; ++i)
        find_Ksum(remainder, i, i1, vals, cur, solutions);
}


int main(int argc, char** argv) {
    std::vector<int> values;
    values.push_back(1);
    values.push_back(2);
    for (int i = 4; i < 12; ++i)
        values.push_back(i);
    for (int i = 13; i < 41; ++i)
        values.push_back(i);
    std::vector<int> tmp;
    std::vector<std::vector<int>> solutions;
    for (int i = 0; i < values.size(); ++i)
        find_Ksum(68, i, values.size() - 1, values, tmp, solutions);

    int n = 0;
    for (auto& s : solutions) {
        if (s.size() == 4) {
            ++n;
            std::cout << "4-sum: ";
            for (auto v : s)
                std::cout << v << ", ";
            std::cout << "\n";
        }
    }
    std::cout << "Number of 4-sums: " << n << "\n";
    std::cout << "Total: " << solutions.size() << "\n";
    return 0;
}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .