2ms Recursive JAVA solution with memorization


  • 1
    B

    Hi guys, share my recursive solution here, you can treat is as top-down DP :)

    public class Solution {
        public int combinationSum4(int[] nums, int target) {
            int[] table = new int[target+1];
            for(int i=0; i<table.length; i++) table[i] = -1;  // for corner case [3,33,333] 10000
            Arrays.sort(nums);
            return helper(nums, table, target);
        }
        
        int helper(int[] nums, int[] t, int tar){
            if(t[tar] >= 0) return t[tar];
            int res = 0;
            for(int i=0; i<nums.length; i++){
                if(tar>nums[i]) res += helper(nums, t, tar-nums[i]);
                else if(tar == nums[i]) {
                    res++;
                    break;
                }
            }
            t[tar] = res;
            return res;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.