What is the complexity of top-to-bottom method?


  • 0
    E
    private int comb(int[] nums, int target, int[] dp) {
            if (dp[target] != -1) return dp[target];
            dp[target] = 0;
            for (int i:nums) {
                if (i <= target) dp[target] += comb(nums, target-i, dp);
            }
            return dp[target];
        }
        public int combinationSum4(int[] nums, int target) {
            int[] dp = new int[target+1];
            dp[0] = 1;
            for (int i = 1; i <= target; ++i) dp[i] = -1;
            return comb(nums, target, dp);
        }
    

    what is the complexity of this method?


Log in to reply
 

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