Better pattern for choosing constructor

I have class Foo, which have more than one constructor.

class Foo
{
public:
Foo( Param1, Param2 );
Foo( Param1, Param3, Param4 );
Foo( Param1, Param4 );
Foo( Param1, Param2, Param4 );

}

Actual list of params to constructor is large and I don't want to provide access to these constructors directly from other projects ( otherwise I would need to export these 4 constructors ). I know best pattern to avoid such multiple constructor is Builder Pattern. But that would create confusion for clients of this class about which param is optional and which param is not. In addition each constructor certain validation based on parameters. So I would need common place to do such validation before actually using any method on this object.

So currently what we are planning is something as below:

1. No change Foo class.

2. Define FooParam Struct
struct FooParam
{
Param1 p1,
Param2 p2,
Param3 p3,
Param4 p4
}

3. Factory:
Foo* CreateFoo( FooParams& foo )
{
if( foo.Param2 )
{
    if( foo.Param4 )
    {
        return new Foo( foo.param1, foo.param2, foo.param4);
    }
    else
         return  new Foo( foo.param1, foo.param2);
}
else if( foo.param4 )
{
      if(foo.param3)
           return new Foo( foo.param1, foo.param3, foo.param4 );
      else
          return new Foo( foo.param1, foo.param4 );
}

throw new Exception("Invalid Parameter" );
}

I think we can do better at step 3. But now sure how?

Can you please help?

Thanks, Kailas