The increase in the number of children with autism and the importance of early autism intervention has prompted researchers to perform automatic and early autism screening. Consequently, in the present paper, a cry-based screening approach for children with Autism Spectrum Disorder (ASD) is introduced which would provide both early and automatic screening. During the study, we realized that ASD specific features are not necessarily observable in all children with ASD and in all instances collected from each child. Therefore, we proposed a new classification approach to be able to determine such features and their corresponding instances. To test the proposed approach a set of data relating to children between 18 to 53 months which had been recorded using high-quality voice recording devices and typical smartphones at various locations such as homes and daycares was studied. Then, after preprocessing, the approach was used to train a classifier, using data for 10 boys with ASD and 10 Typically Developed (TD) boys. The trained classifier was tested on the data of 14 boys and 7 girls with ASD and 14 TD boys and 7 TD girls. The sensitivity, specificity, and precision of the proposed approach for boys were 85.71%, 100%, and 92.85%, respectively. These measures were 71.42%, 100%, and 85.71% for girls, respectively. It was shown that the proposed approach outperforms the common classification methods. Furthermore, it demonstrated better results than the studies which used voice features for screening ASD. To pilot the practicality of the proposed approach for early autism screening, the trained classifier was tested on 57 participants between 10 to 18 months. These 57 participants consisted of 28 boys and 29 girls and the results were very encouraging for the use of the approach in early ASD screening.