LeetCoding Challenge Oct. 2: Combination Sum

LeetCode の October Challenge 2 日目。

今日は Combination Sum です。

問題の概要

• 配列で与えられる複数個の数値をそれぞれ 0 回以上使い、その合計値が target となるような数値の組み合わせをすべて列挙する

実装の手順・考え方の推移

• これは動的計画法使って計算量を削減する必要のありそうな問題だな… 🤔
• ひとまず再帰を使おう
  • それぞれのメソッド呼び出しにおいては、 [index, candidates.length) の範囲をループして、candidates[i] の数値を 1 回以上使うようにしよう
  • 再帰呼び出しでは [i + 1, candidates.length) の範囲がループされるようにしよう
• candidate.length * target の大きさの配列 (constraints より最大で 1.5 万) を用意してここに中間結果をキャッシュすればいいのでは？
• 試行錯誤して実装 → submit → accept 🤗
  • しかしながら runtime 28 ms で Your runtime beats 5.80 % of java submissions.
    • これはひどい… 🤮
• 最頻値の実行時間のコードサンプルを見てみたけど、これはキャッシュとかせずにナイーブな実装にした方が速いやつだった。つらい

コード

@SuppressWarnings({"unchecked", "rawtypes"})
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return recursive(candidates, target, 0, 0, new List[candidates.length * target]);
    }

    List<List<Integer>> recursive(int[] candidates, final int target, final int index, final int sum, List[] cache) {
        if (sum >= target || index >= candidates.length) {
            return Collections.emptyList();
        }

        int cacheIndex = sum * candidates.length + index;
        List<List<Integer>> result = (List<List<Integer>>) cache[cacheIndex];
        if (result != null) {
            return result;
        }

        result = new ArrayList<>();

        for (int i = index; i < candidates.length; i++) {
            List<Integer> nums = new ArrayList<>(target);
            int c = candidates[i];
            int s = sum + c;
            nums.add(c);

            while (s < target) {
                List<List<Integer>> recResult = recursive(candidates, target, i + 1, s, cache);
                for (List<Integer> r : recResult) {
                    List<Integer> list = new ArrayList<>(nums.size() + r.size());
                    list.addAll(nums);
                    list.addAll(r);
                    result.add(list);
                }

                nums.add(c);
                s += c;
            }

            if (s == target) {
                result.add(nums);
            }
        }

        cache[cacheIndex] = result;

        return result;
    }
}