#include<iostream>
#include<bits/stdc++.h>
using namespace std;


class Solution {
public:
    int ans = 0x3f;
    int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
         //回溯
         for(auto &e:baseCosts)
         dfs(0,e,target,toppingCosts);
         return ans;//或者用引用传入
    }
    void dfs(int index,int sum,int target,vector<int>& top)
    {
        //cout<<index<<" "<<endl;
        cout<<sum<<" "<<ans<<endl;
        if(abs(ans-target)<sum-target)return;
        //if(sum>target)return;
        else{
            if(abs(ans-target)>=abs(sum-target))
            {
               // cout<<sum<<" "<<ans<<endl;
                if(abs(ans-target)>abs(sum-target))
                {
                    ans = sum;
                    
                }
                else
                ans = min(ans,sum);//两者取小
                // ans = ans>sum?sum:ans;
               // cout<<sum<<" "<<ans<<endl;
            }
        }
        if(index == top.size())return;
        dfs(index+1,sum+top[index],target,top);
        dfs(index+1,sum+(top[index]*2),target,top);
       //cout<<ans<<endl;
        
        dfs(index+1,sum,target,top);
    }
};

// class Solution {
// public:
//     void dfs(const vector<int>& toppingCosts, int p, int curCost, int& res, const int& target) {
//         if (abs(res - target) < curCost - target) {
//             return;
//         } else if (abs(res - target) >= abs(curCost - target)) {
//             if (abs(res - target) > abs(curCost - target)) {
//                 res = curCost;
//             } else {
//                 res = min(res, curCost);
//             }
//         }
//         if (p == toppingCosts.size()) {
//             return;
//         }
//         dfs(toppingCosts, p + 1, curCost + toppingCosts[p] * 2, res, target);
//         dfs(toppingCosts, p + 1, curCost + toppingCosts[p], res, target);
//         dfs(toppingCosts, p + 1, curCost, res, target);
//     }

//     int closestCost(vector<int>& baseCosts, vector<int>& toppingCosts, int target) {
//         int res = *min_element(baseCosts.begin(), baseCosts.end());
//         for (auto& b : baseCosts) {
//             dfs(toppingCosts, 0, b, res, target);
//         }
//         return res;
//     }
// };


  struct TreeNode {
      int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };
 
class Solution {
public:
    unordered_map<int,int> mp;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        for(int i = 0;i<preorder.size();i++)
        {
            mp[inorder[i]] = i;
        }
        return dfs(preorder,inorder,0,n-1,0,n-1);
    }
    TreeNode* dfs(vector<int>& preorder,vector<int>& inorder,int pl,int pr,int il,int ir)
    {
        if(pl>pr)return nullptr;
        int pos = mp[preorder[pl]];
        int k = pos-il;
        TreeNode* root = new TreeNode(preorder[pl]);
        root->left = dfs(preorder,inorder,pl+1,pl+k,il,il+k-1);
        root->right = dfs(preorder,inorder,pl+k+1,pr,il+k+1,ir);
        return root;
    }
};

int main()
{
    return 0;
}