Great approach. Learned a new pattern of backtracking with subtle dp. I convert your solution to C++.

class Solution {
map<vector<int>, int> mp;
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
if(mp.count(needs))
return mp[needs];
int res = INT_MAX;
for(auto s : special) {
vector<int> newNeeds(needs.begin(), needs.end());
bool validSpecial = true;
for(int i = 0; i < needs.size(); ++i) {
newNeeds[i] -= s[i];
if(newNeeds[i] < 0) {
validSpecial = false;
break;
}
}
if(validSpecial)
res = min(res, s.back() + shoppingOffers(price, special, newNeeds));
}
int normalPrice = 0;
for(int i = 0; i < needs.size(); ++i)
normalPrice += (price[i]*needs[i]);
res = min(res, normalPrice);
return mp[needs] = res;
}
};