638. Shopping Offers

https://leetcode.com/problems/shopping-offers/description/
bool operator<(vector<int>& s, vector<int>& n) {
    for(int i=0; i<n.size(); i++) {
        if(s[i]>n[i]) return false;
    }
    return true;
}
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int res = INT_MAX;
        shop(price, special, 0, needs, res, 0);
        return res;
    }
    void shop(vector<int>& price, vector<vector<int>>& special, int s, vector<int> needs, int&res, int sum){
        int I = price.size();
        if(s == special.size()) {
            for(int i=0; i<I; i++) sum += price[i] * needs[i];
            if(sum < res) res = sum;
            return;
        }
        shop(price, special, s+1, needs, res, sum);
        if(special[s]<needs)
        do {
            for(int i=0; i<I; i++) {
                needs[i] -= special[s][i];
            }
            sum += special[s][I];
            shop(price, special, s+1, needs, res, sum);
        } while(special[s]<needs);
       
    }
};