Menu Combination Sum, C++ (gcc)

Menu Combination Sum

/* 22 Menu Combination Sum
Given a menu (list of items prices), find all possible combinations of items that sum a particular value K. 
(A variation of the typical 2sum/Nsum questions).
*/

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void dfs(vector<vector<double>>& res, vector<double>& v, vector<double>& menu, long target, int idx){
    if(target == 0) { // find one solution 
        res.push_back(v); return;
    }
    if(target<0) return;
    
    for(int i=idx; i<menu.size(); i++) {
        if(menu[i]*100 == 0) continue;
        if(i>=1 && menu[i] == menu[i-1]) continue;
        v.push_back(menu[i]);
        dfs(res, v, menu, target - 100*menu[i], i); // i not idx
        v.pop_back(); 
    }
}

vector<vector<double>> findAll(vector<double> menu , double target){
    vector<vector<double>> res;
    vector<double> v; 
    sort(menu.begin(), menu.end()); 
    dfs(res, v, menu, target*100, 0);  //
    return res;
}

int main(){
    vector<double> v = {0.1, 0.2, 0.2, 04};
    vector<vector<double>> res = findAll(v, 0.4); 
    for(auto x: res){
        cout << "[";
        for(auto y: x)
            cout << y <<  " ";
        cout << "]" << endl;
    }
    return 0; 
}


run \| edit \| history \| help	0