Count all unique subsets with Sum S

Question

Team 7 faces a horrible foe. He can only be defeated with a special quadruple combination attack of strength (\$1 <=S <= 10^9\$). Naruto, Sasuke, Sakura and Kakashi must attack simultaneously to perform the combo. Each of them can choose from \$N\$ (\$1 <= N <=1000\$) attacks, having strengths \$si\$ each (\$0 <= i < N\$, \$1 <= si <=10^9\$). The strengths of individual attacks add up to form the strength of the combo.

Is there a valid combination that they can use? Note that the same attacks are available to all of them.

You are required to write a function which takes input as follows:

An integer \$N\$ as number of attacks, an integer vector s[] as the strengths of \$N\$ attacks and an integer S as the required strength of the combo. Set the output variable to the number of distinct valid combos.

Two combinations are different if they differ in strength of at least one attack used.

Input: 1 {1} 4
Output: 1 ===> {1,1,1,1}

Input: 2 {1,2} 5
Output: 1 ===> {1,1,1,2}

#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>

const int noOfPalyers = 4;

int validCombo(int input1,int input2[],int input3)
{
    std::cout<< "-----------------------------------------------------------------------------"<<"\n";
    int count = 0;
    std::vector<int> vec;
    int size =input1*noOfPalyers;
    for(int i = 0; i < input1; i++)
    {
        for(int j = 0; j < noOfPalyers;j++)
        {
            vec.push_back(input2[i]);
        }
    }

    std::vector< std::vector< std::pair<int, int> > > vecHash;

    for(int i =0; i < (size*size); i++)
    {
        vecHash.push_back(std::vector< std::pair<int, int> > ());
    }

    for(int i =0; i < size; i++)
    {
        for(int j =1; j < size; j++)

        {
            int key = vec[i] + vec[j];
            if(vec[i]<= vec[j])
                vecHash[key].push_back(std::make_pair(vec[i], vec[j]));
            else
                vecHash[key].push_back(std::make_pair(vec[j], vec[i]));

        }
    }

    std::set< std::vector<int> > solution;
    for(int i = 0; i < input3; i++)
    {

        if(vecHash[input3 - i].size() > 0)
        {
            for(int k = 0; k < vecHash[i].size() ; k++)
            {
                std::pair<int, int> fPair = vecHash[i][k];

                for(int m =0; m < vecHash[input3 - i].size(); m++)
                {
                    std::pair<int, int> sPair = vecHash[input3 - i][m];
                    std::vector<int> vec;
                    vec.push_back(fPair.first);
                    vec.push_back(fPair.second);
                    vec.push_back(sPair.first);
                    vec.push_back(sPair.second);
                    std::sort(vec.begin(), vec.end());
                    solution.insert(vec);
                }

            }
        }
    }


    std::set< std::vector< int> >::iterator it;
    for (it = solution.begin(); it != solution.end(); it++) 
    {
        std::cout<< "\n";
        for(int i = 0; i < (*it).size(); i++) 
            std::cout << (*it)[i] << " , ";
        std::cout<< "\n";
    }
    count = solution.size();


    std::cout << "solution size = "  << solutionSet.size();
    std::cout<< "\n";
    std::cout<< "\n";

    std::cout<< "-----------------------------------------------------------------------------"<<"\n";

    return count;

}

int  main()
{
    int i = 3;
    int arr[] = {1,2,3};
    int j = 7;
    int arr1[] ={1};
    std::cout <<"o/p == "  << validCombo(i, arr, j)<< "\n";
    std::cout <<"o/p == "  << validCombo(1, arr1, 4);


    getchar();
    return 0;
}

Answer 1

A lot of your vector initialization can be handled by vector's constructor. Not only is that much shorter and less error prone, it's also more efficient since it lets the vector avoid resizing over and over again.

As an example:

std::vector< std::vector< std::pair<int, int> > > vecHash;

for(int i =0; i < (size*size); i++)
{
    vecHash.push_back(std::vector< std::pair<int, int> > ());
}

This can be:

std::vector< std::vector< std::pair<int, int> > > vecHash(size*size);

---

if(vecHash[input3 - i].size() > 0)

This should be if(!vecHash[input3 - i].empty()) as empty() reads clearer.

---

Your logic and your IO should be handled separately. You should add a function for printing solutions so your validCombo isn't doing quite so much. That will mean returning the solutions instead of the number of solutions, but that makes more sense anyway.

For small little programs like this it doesn't really matter, but for anything non-trivial, you want each function to only do one thing. That allows you to control and modify things in a much easier way. (Even though we're not talking about OOP, this is essentially the essence of the SRP.

---

count = solution.size();
std::cout << "solution size = "  << solutionSet.size();

// ...

return count;

Either use count consistently, or don't bother assigning it.

Also, declare variables as close to use as possible. It's confusing to try to figure out where in the world count came from when it's declared a few dozen lines up.

Answer 2

• noOfPalyers is misspelled; it should be noOfPlayers. Better yet, make it numberOfPlayers.

• It's usually more common to have a space after the #include directive. Also, consider ordering the libraries in some way for easier lookup, such as alphabetically.

• Since you already use std::vector, just use it in place of all C-arrays. You especially shouldn't pass C-arrays to functions as they decay to pointers that way. Always try to avoid this in C++.

• Instead of including <stdio.h> just for getchar(), use std::cin.get() for doing a "pause" at some point in the program. This is also already part of <iostream>.

• Instead of using (*it).size(), use the clearer -> operator: it->size().

• Some of your variable names are not descriptive. What is arr[] supposed to hold? To which structure does size correspond? Be sure to use clearer names so that it's easier for others - and even yourself in the future - to understand their significance.