This is a great puzzle which spectacularly combines two previous golf outings. I took the route of least resistance -- instead of bothering with parenthesis, I used reverse-polish notation expressions. This significantly simplified things:

sub c {@r='';@r=map{$c=$_;map"$c $_",@r}@_ for 1..shift;@r}
sub puzzle {
  ($x,$q,@l)=@_;@l=c$q,@l;@o=c$q-1,qw'+ - / *';
  map{$n=$_;map{$t=$n.$_;{$t=~s!(\S+)\s+(\S+)\s*([-+*/])!"$1$3 $2"!ee&
+&redo};
  $t eq"$x "?$n.$_:()}@o}@l
}

## example usage: puzzle ($total, $size, @numbers) ##
print join $/, puzzle(24, 4, 6, 9);
6 6 6 6 + + + 
6 6 6 9 / * * 
6 6 9 6 - * + 
6 6 9 6 / / * 
6 9 6 6 * / /
[download]

That code is somewhat golfed, and damn messy, so I'm sure it can be significantly improved upon.

   MeowChow                                   
               s aamecha.s a..a\u$&owag.print