[C++] DFS Backtracking Solution
\nclass Solution {\npublic:\n    set<int> val;\n    void calc(vector<int> &li, vector<int>& toppingCosts){\n        int cur = 0;\n        for(int i=0;i<toppingC
```\nclass Solution {\npublic:\n    set<int> val;\n    void calc(vector<int> &li, vector<int>& toppingCosts){\n        int cur = 0;\n        for(int i=0;i<toppingCosts.size();++i)\n            if(li[i] > 0) cur += toppingCosts[i]*li[i];\n        val.insert(cur);\n    }\n    void dfs(int cur, vector<int> &li, vector<int>& toppingCosts){\n        if(cur >= li.size()){\n            calc(li,toppingCosts);\n            return;\n        }\n        li[cur] = 0;\n        dfs(cur+1,li,toppingCosts);\n        li[cur] = 1;\n        dfs(cur+1,li,toppingCosts);\n        li[cur] = 2;\n        dfs(cur+1,li,toppingCosts);\n    }\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        vector<int> li(toppingCosts.size(),0);\n        dfs(0,li,toppingCosts);\n        int ans = INT_MAX, sign = 1;\n        for(int i:baseCosts){\n            int want = target-i;\n            for(int j:val){\n                if(want-j >= 0 && want-j <= ans){ans = want-j;sign=1;}\n                else if(want-j<0 && j-want<ans){ans=j-want;sign=0;}\n            }\n        }\n        if(sign) return target-ans;\n        else return target+ans;\n    }\n};\n```
['Backtracking', 'Depth-First Search', 'C', 'C++']