DFS Search (brute-force vs tree truncation) (time: O(n*3^m), space: O(m))
Intuition\nImagine a dfs tree search, start from one of n bases cost, you can pick 1 topping from m toppings. You have 3 options (tree branches): add 0, 1, 2 of
# Intuition\nImagine a dfs tree search, start from one of n bases cost, you can pick 1 topping from m toppings. You have 3 options (tree branches): add 0, 1, 2 of current topping.\n\n# Approach\nDFS search.\nPlus version: terminate current tree branch search if current (cost >= target && dist_to_target(current_cost) >= dist_to_target(global_min_cost)).\n\n# Complexity\n- Time complexity:\nO(n*3^m)\n\n- Space complexity:\nO(m)\n\n# Code\n```\nclass Solution {\npublic:\n    int dist_target(int &cur_cost, int &target) {\n        return abs(cur_cost - target);\n    }\n    void topping_dfs(vector<int>& toppingCosts, int top_ind, int cur_cost, int &min_cost, int &target) {\n        if (dist_target(cur_cost, target) < dist_target(min_cost, target)){\n            min_cost = cur_cost;\n        }\n        else if (dist_target(cur_cost, target) == dist_target(min_cost, target) && cur_cost < min_cost) {\n            min_cost = cur_cost;\n        }\n        if (top_ind >= toppingCosts.size()) {\n            return;\n        }\n        if (cur_cost < target || dist_target(cur_cost, target) < dist_target(min_cost, target)) {\n            topping_dfs(toppingCosts, top_ind+1, cur_cost + 0*toppingCosts[top_ind], min_cost, target);\n            topping_dfs(toppingCosts, top_ind+1, cur_cost + 1*toppingCosts[top_ind], min_cost, target);\n            topping_dfs(toppingCosts, top_ind+1, cur_cost + 2*toppingCosts[top_ind], min_cost, target);\n        }\n        // topping_dfs(toppingCosts, top_ind+1, cur_cost + 0*toppingCosts[top_ind], min_cost, target);\n        // topping_dfs(toppingCosts, top_ind+1, cur_cost + 1*toppingCosts[top_ind], min_cost, target);\n        // topping_dfs(toppingCosts, top_ind+1, cur_cost + 2*toppingCosts[top_ind], min_cost, target);\n    }\n\n    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {\n        int min_cost = 1e8;\n        for (int i = 0; i < baseCosts.size(); i++) {\n            topping_dfs(toppingCosts, 0, baseCosts[i], min_cost, target);\n        }\n        \n        return min_cost;\n    }\n};\n```
['C++']