class Solution {
public:
    void helper(vector<int>& nums, int& res, int target, int curSum, int idx, int k){
        if(k==0){
            res = curSum<target? res+1:res;
            return;
        }
        
        for(int i=idx; i<nums.size(); i++){
            curSum = curSum+nums[i];
            helper(nums, res, target, curSum, i+1, k-1);
            curSum = curSum-nums[i];
        }
    }

    int threeSumSmaller(vector<int>& nums, int target) {
        int res=0;
        int curSum=0;
        if(nums.empty())
            return res;
        helper(nums, res, target, curSum, 0, 3);
        return res;
    }
};