First contacted by a college recruiter. Then had an on-campus interview that covered my resume and some technical questions. Within a few days, I was invited to Redmond. They provided all utilities, hotel, and flight arrangements.

At the on-site interview, I met with 4 different interviewers. It was basically the same format: resume + general questions and technical questions. One of the questions was, given an array of integers and a sum, to see whether there is a combination that adds up to the sum. I answered all technical questions for the first two interviews, but lost focus after lunch. You better prepare for a long day. The last interview especially seems to be the deciding one.

Given an array of integers and a sum, check whether any combination adds up to the sum. Please solve and program in any language.