Slow execution time of search algorithm
I think in this case the answer is to count rather than sort and search. I would create a struct that simply keeps count of how many cards of each type. Something like this:

struct cardCounts {
    unsigned long numOneCircles;
    unsigned long numTwoCircles;
    unsigned long numThreeCircles;
    unsigned long numOneSquares;
    unsigned long numTwoSquares;
    unsigned long numThreeSquares;
    unsigned long numOneTriangles;
    unsigned long numTwoTriangles;
    unsigned long numThreeTriangles;
};


You can initialize them all to 0, then increment each one as you read a card of that type from the input.

Once you've read all the cards, you can make combinations from them. For example, you can figure out how many sets containing 3 cards of 1 circle are possible by simply dividing numOneCircles by 3. Then the same for each other member of the struct. 

Next, you can find combinations where 1 property is the same and the other are all different. So either the shape is the same but the counts are different, or the counts are the same and the shapes are different. You can take the minimum of numOneCircles, numTwoCircles, and numThreeCircles, and that's how many sets you can make with 1 card from each stack. Do the same for squares then triangles. Then switch it so the number stays the same but the shapes are different - so across numOneCircles, numOneSquares, and numOneTriangles.

Finally, find all combinations where both the shape and the number are different. This one is a little trickier, but not too bad. Check for one circle, two squares, three triangles. (Again, taking the min of those 3 as the result.) Then one circle, two triangles, three squares. There are 9 combinations you have to cover (I think?).

This should be O(n) in time and O(1) in space, as you'll only read through the data once when counting up the amounts, and you'll only ever use the 9 elements to store the sums.