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

• 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;
}
}
``````

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