Swift Solution DFS O(M* 3^N)
```\nclass Solution {\n    func closestCost( baseCosts: [Int], _ toppingCosts: [Int], _ target: Int) -> Int {\n        var closest = Int.max\n        var dict =
```\nclass Solution {\n    func closestCost(_ baseCosts: [Int], _ toppingCosts: [Int], _ target: Int) -> Int {\n        var closest = Int.max\n        var dict = [Int: [Int]]()\n    \n        func dfs(_ remaining: Int, _ index: Int, _ sum: Int) {\n            if index >= toppingCosts.count  {\n                dict[target - sum, default: []].append(sum)\n                return\n            }\n            \n            dfs(remaining, index + 1, sum)\n            dfs(remaining - toppingCosts[index], index + 1, sum +  toppingCosts[index])\n            dfs(remaining - toppingCosts[index] - toppingCosts[index], index + 1, sum +  toppingCosts[index] + toppingCosts[index])\n        }\n        \n        for i in baseCosts {\n            dfs(target - i, 0, i)\n        }\n        \n        let array1 = dict.keys.filter { $0 < 0 }.sorted { $0 > $1 }\n        let array2 = dict.keys.filter { $0 >= 0}.sorted()\n        \n        if let key1 = array1.first, let key2 = array2.first {\n            if abs(key1) < abs(key2) {\n                return dict[key1]?.first ?? -1\n            }\n\n            return dict[key2]?.first ?? -1\n        }\n        \n        if let key = array1.first {\n            return dict[key]?.first ?? -1 \n        }\n        \n        return dict[array2.first ?? -1]?.first ?? -1 \n    }\n}
[]