0/1 Knapsack
IntuitionWorks for n = 1000, m = 1000Approach0/1 knapsack. No need of DFS. Works for n = 1000Complexity
Time complexity:
O(target*m)
Space complexity:
Code
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Works for n = 1000, m = 1000

# Approach
<!-- Describe your approach to solving the problem. -->
0/1 knapsack. No need of DFS. Works for n = 1000

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->
O(target*m)

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class Solution {
public:
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int og_target) {
        int target = 2*og_target;
        int n = baseCosts.size(), m = toppingCosts.size();
        vector<bool> sums(target+1,false);
        sums[0] = true;
        for(int t = 0;t < m;t++){
            for(int j = 0;j<2;j++){
                int tc = toppingCosts[t];
                for(int i = target - tc;i >= 0; i--){
                    if(sums[i]) sums[i+tc] = true;
                }
            }
        }
        vector<int> possible_sums;
        for(int i = 0;i<=target;i++){
            if(sums[i]) possible_sums.push_back(i);
        }
        int sz = possible_sums.size();
        long long ans = INT_MAX;
        int least_difference = INT_MAX;
        auto func = [&](int a){
            int dif = a - og_target;
            if(abs(dif) < least_difference){
                least_difference = abs(dif);
                ans = a;
            }else if(abs(dif) == least_difference){
                if(a < ans) ans = a;
            }
        };
        for(int i =0 ;i<n;i++){
            int rem = og_target - baseCosts[i];
            func(baseCosts[i]);
            int idx = lower_bound(possible_sums.begin(), possible_sums.end(), rem) - possible_sums.begin();
            if(idx < sz) func(baseCosts[i] + possible_sums[idx]);
            if(idx > 0) func(baseCosts[i] + possible_sums[idx-1]);
        }
        return ans;
    }
};
```
['C++']