LeetCoding Challenge Oct. 2: Combination Sum

문제의 개요

실시의 절차, 생각의 추이

코드

@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;
    }
}