Possible total scores for n score lists

[Code Apperentice]

The solution to this problem I thought up is probably very simple but I can't think of it.

Basically I have n score lists. Each score list has i scores. I want to get all possible combinations from the n score lists with one number taken from each list.

For example, let's say I have 3 score lists with i of (3, 2, 2) respectively.

2, 4, 5
1, 2
9, 0

Then I want to get the possible obtainable scores like (2 + 1 + 9) (2 + 1 + 0) (2 + 2 + 9) (2 + 2 + 0) and so on and store them in a container of type set so it doesn't have duplicates.

I thought of using trees? But I don't know how to implement it

[Golden Lizard]

A naive solution is to make all sums in O(size(score1)*size(score2)*size(score3)) time:

for(auto i: scores1)
 for(auto j: scores2)
  for(auto k: scores3)
    sums.push_back(scores1[i]+scores2[j]+scores3[k]);

You can also use dynamic programming to cut the execution time by memoizing previous sums.

[gunnerfunner]

Use a map? and multimap for non-uniques as well ...

#include <iostream>
#include <vector>
#include <map>
#include <tuple>

int main()
{
    std::vector<int> a {2, 4, 5};
    std::vector<int> b {1, 2};
    std::vector<int> c {9, 0};

    std::map<int, std::tuple<int, int, int>> myMap;

    for (auto itr_a = a.begin(); itr_a != a.end(); ++itr_a)
    {
        for (auto itr_b = b.begin(); itr_b != b.end(); ++itr_b)
        {
            for (auto itr_c = c.begin(); itr_c != c.end(); ++itr_c)
            {
                myMap.insert(std::make_pair((*itr_a + *itr_b + *itr_c), std::make_tuple (*itr_a, *itr_b, *itr_c)));
            }
        }
    }
    for (auto& elem : myMap)
    {
        std::cout << elem.first << ": " << std::get<0>(elem.second) << " "
            << std::get<1>(elem.second) << " " << std::get<1>(elem.second) << "\n";
    }
}

Output

3: 2 1 1
4: 2 2 2
5: 4 1 1
6: 4 2 2
7: 5 2 2
12: 2 1 1
13: 2 2 2
14: 4 1 1
15: 4 2 2
16: 5 2 2

[JLBorges]

#include <iostream>
#include <vector>
#include <set>

using score_list = std::vector<int> ;

std::set<int> possible_total_scores( std::vector<score_list>::const_iterator begin,
                                     std::vector<score_list>::const_iterator end )
{
    std::size_t nlists = end - begin ;

    if( nlists == 0 ) return {} ; // no score lists; return empty set

    else if( nlists == 1 ) return { begin->begin(), begin->end() } ; // only one score list, return the unique values in it

    else // two ore more score lists
    {
        // get possible total scores for the tail (every list except the first)
        const std::set<int> tail = possible_total_scores( begin+1, end ) ;
        
        std::set<int> result ;
        // add every score in the first list to each possible_total_score for the tail
        for( int score : *begin ) for( int total : tail ) result.insert(score+total) ;
        return result ;
    }
}

int main()
{
    std::vector<score_list> score_lists =
    {
        { 2, 4, 6 },
        { 2, 8 },
        { 4, 6 },
        { 4, 6, 8, 8 },
        { 0, 2, 4, 6, 8, 8 },
        { 4, 4, 4, 8, 8, 8, 8 },
        { 0, 0, 0, 2, 2, 2, 4, 4, 4, 6, 6, 6, 8, 8, 8 },
        { 7, 7, 7, 9, 9, 9, 9 }
    };

    const auto set = possible_total_scores( score_lists.begin(), score_lists.end() ) ;
    int n = 0 ;
    for( int total_score : set ) std::cout << ++n << ". " << total_score << '\n' ;
}

http://coliru.stacked-crooked.com/a/c4b76252b816dd26

[Code Apperentice]

Thanks everyone, JLBorges was the best because it took into account the variable size of the score list