Multi-Agent Plan Recognition (MAPR) seeks to identify the dynamic team structures and team behaviors from the observed activity sequences (team traces) of a set of intelligent agents, based on a library of known team activity sequences (team plans). Previous MAPR systems require that team traces and team plans are fully observed. In this paper we relax this constraint, i.e., team traces and team plans are allowed to be partial. This is an important task in applying MAPR to real-world domains, since in many applications it is often difficult to collect full team traces or team plans due to environment limitations, e.g., military operation. This is also a hard problem since the information available is limited. We propose a novel approach to recognizing team plans from partial team traces and team plans. We encode the MAPR problem as a satisfaction problem and solve the problem using a state-of-the-art weighted MAX-SAT solver. We empirically show that our algorithm is both effective and efficient.