LeetCode 2020-11-27: Partition Equal Subset Sum

Partition Equal Subset Sum (medium) の挑戦メモです。

問題の概要

• 与えられた数値の配列の要素を、以下の条件を満たす二つの集合に割り振ることができるか否かを判定する
  • それぞれの集合に割り振られた値を合計したときに、両者の集合の合計が等しくなる

考え方

• 基本的には、配列のそれぞれの要素について「どちらかの集合に割り振ってみる」のを繰り返すことになるのかな？
  • ナイーブにやれば総当りになるので時間計算量は $O(2 ^ n)$ になると思われるが… 😨
    • 配列の長さは最長で 200 なので、ナイーブなやり方は無理だろう…
  • 枝刈りしていかに不要な計算をしないようにするかを考える必要があるようだ 🤔
• 動的計画法なやり方でチャレンジしてみよう
  • 配列の先頭もしくは末尾から走査をするとして、i 番目の要素を集合 A に放り込んだ場合の結果と集合 B に放り込んだ場合の結果を再帰処理で得ることを考える
  • このとき、集合 A の要素の その時点での合計値 をキーにして、結果を boolean[] なテーブルに記録しておく
  • 走査を進めていくと、要素の割り振り状況によって集合 A のその時点での合計値がすでに過去に処理したものと等しいケースが出てくるので、それを boolean[] なテーブルを使って枝刈りすればよさそう
• 早速実装して submit → 幾度か wrong answer を喰らいつつも accept
  • Runtime 3ms で Your runtime beats 96.67 % of java submissions. なので、まだ改善の余地があるようだ
• 枝刈りを工夫したり、数値ごとに事前に頻度を集計して利用するなどして 1ms Your runtime beats 99.51 % of java submissions. まで縮められたが、これが限界のようだ…

コード

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        int max = 0;
        int[] freq = new int[101];
        for (int num : nums) {
            total += num;
            freq[num]++;
            max = Math.max(max, num);
        }

        if ((total & 1) == 1) {
            return false;
        }

        if (max > (total >> 1)) {
            return false;
        }

        int prev = 0;
        for (int i = 1; i < max; i++) {
            if (freq[i] > 0) {
                prev = i;
            } else {
                freq[i] = -prev;
            }
        }

        return canPartitionRecursive(freq, max, 0, 0, total >>> 1, new boolean[100 * 200]);
    }

    boolean canPartitionRecursive(int[] freq, int num, int sumA, int sumB, int target, boolean[] traversed) {
        if (sumB > target) {
            return false;
        }

        if (traversed[sumA]) {
            return false;
        }

        if (freq[num] < 0) {
            return canPartitionRecursive(freq, -freq[num], sumA, sumB, target, traversed);
        }

        for (int i = 0, a = 0, b = num * freq[num];
             i <= freq[num] && sumA + a <= target;
             i++) {
            if (sumA + a == target
                    || canPartitionRecursive(freq, num - 1, sumA + a, sumB + b, target, traversed)) {
                return true;
            }

            a += num;
            b -= num;
        }

        traversed[sumA] = true;

        return false;
    }
}