bit演算を用いて、 \(0\) 以上 \(2^n\) 未満の整数であって丁度 \(k\) 個のbitが立っているようなものを \(O(_n C _k)\) 時間で列挙することができます。

for (int s = (1 << k) - 1;s < 1 << n;) {
  // この時点のsは条件を満たした整数
  int t = s | s - 1;
  s = t + 1 | (~t & -~t) - 1 >> Integer.numberOfTrailingZeros(s) + 1;
}

ここで、numberOfTrailingZerosは \(O(1)\) なのか？と疑問に思うかもしれません。 しかし、例えば次のような実装を行うことで \(O(1)\) で求めることができるため、計算量上は問題ありません。

static int[] deBrujin32 = {0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
int numberOfTrailingZeros(int x) {
  if (x == 0) return 32;
  return deBrujin32[(x & -x) * 0x077CB531 >>> 27];
}

これを用いれば、この問題は \(O( _{H_1} C _{H_2} \ _{W_1} C_{W_2} \ H_2 \ W_2) = O(\frac{2^{H_1 + W_1} H_2 W_2}{\sqrt{ H_1 W_1}})\) で解くことができます。

参考: bit演算による集合の列挙