C#: Easy to Understand 2 Solutions. 1st: Simple Recursive and 2nd: DP Solution.


  • 0

    Solution 1: Simple Recursive Solution. (TLE)

    public class Solution {
        public int CombinationSum4(int[] nums, int target) {
            if (target < 0)
                return 0;
            else if (target == 0)
                return 1;
            else {
                int res = 0;
                for (int i = 0; i < nums.Length; i++)
                    res += CombinationSum4(nums, target - nums[i]);
                return res;
            }
        }
    }
    

    Solution 2: Converting Solution 1 to DP (storing calculated results) (Accepted)

    public class Solution {
        public int CombinationSum4(int[] nums, int target) {
            int[] dp = new int[target + 1];
            for (int i = 0; i < dp.Length; i++)
                dp[i] = -1;
            dp[0] = 1;
            return Helper(nums, target, dp);
        }    
        private static int Helper(int[] nums, int target, int[] dp) {           
            if (target < 0)
                return 0;
            if (dp[target] != -1)    //Check is result already exists.
                return dp[target];  
            int res = 0;
            for (int i = 0; i < nums.Length; i++)
                    res += Helper(nums, target - nums[i], dp);
            dp[target] = res;       //Store the calculated result.
            return res;
        }    
    }
    

Log in to reply
 

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