この問題は俗に半分全列挙と呼ばれる手法により解くことができます。

各薬品に対して「使わない」「通常モードで使う」「加熱モードで使う」の 3 つの選択肢があるため、薬品の使い方の組み合わせは \(3^N\) 通りあります。そのため、全ての組み合わせを愚直に調べることはできません。

薬品を \(N/2\) 個ずつにわけ、前半と後半と呼ぶことにします。後半の薬品について \(3^{N/2}\) 通りを愚直に調べることで、後半の薬品を用いて作ることができる溶液の量を全通り列挙することができます。これを set で管理することで、「前半の薬品の使い方を決めたとき、合計で \(K\) mL になるような後半の薬品の使い方は存在するか？」を高速に判定することができます。

後半の列挙に \(O(3^{N/2})\) 、前半の \(O(3^{N/2})\) 通りの各決め方に対し後半の決め方をチェックするのに \(O(\log 3^{N/2})\) ないし expected \(O(1)\) となるため、全体で \(O(N3^{N/2})\) ないし expected \(O(3^{N/2})\) の計算量でこの問題を解くことができます。

この問題のように、対象を前半と後半の 2 つに分け、前半を全探索しながら、それぞれに対し後半を高速に求める手法を俗に 半分全列挙 と呼びます。

実装例 (C++)

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

int main(){
  int n;
  long long k;
  cin >> n >> k;
  vector<pair<long long, long long>>ab(n);
  for(int i=0; i<n; i++) cin >> ab[i].first >> ab[i].second;

  auto f=[&](vector<pair<long long, long long>>ab){
    // 与えられた薬品で作れる溶液量を列挙する
    vector<long long>ret({0});
    for(auto[a, b]: ab){
      int n = ret.size();
      for(int i=0; i<n; i++){
        ret.push_back(ret[i] + a);
        ret.push_back(ret[i] + b);
      }
    }
    return ret;
  };

  vector<pair<long long ,long long>>zenhan(ab.begin(), ab.begin() + n/2);
  vector<pair<long long ,long long>>kouhan(ab.begin() + n/2, ab.end());
  auto xvec = f(zenhan);
  auto yvec = f(kouhan);
  set<long long>yset(yvec.begin(), yvec.end());

  for(auto x: xvec){
    if(yset.contains(k-x)){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}

実装例 (Python)

N, K = map(int, input().split())
AB = []
for _ in range(N):
  A, B = map(int, input().split())
  AB.append((A, B))

def f(AB):
  # 与えられた薬品で作れる溶液量を列挙する
  ret = [0]
  for a, b in AB:
    N = len(ret)
    for i in range(N):
      ret.append(ret[i] + a)
      ret.append(ret[i] + b)
  return ret

X = f(AB[:N//2])
Y = set(f(AB[N//2:]))

for x in X:
  if K-x in Y:
    print("Yes")
    exit()
print("No")