# Correct numerically but overflow solution (because of factorial)

• ``````public class Solution {
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
return dfs(nums, new int[nums.length], 0, 0, target);
}

private int dfs(int[] nums, int[] count, int index, int sum, int target) {
if (index == nums.length) {
return countCombinations(count, sum, target);
}
int ret = 0;
for (int i = 0; sum + i * nums[index] <= target; i++) {
count[index] = i;
ret += dfs(nums, count, index + 1, sum + i * nums[index], target);
count[index] = 0;
}
return ret;
}

private int countCombinations(int[] count, int sum, int target) {
if (sum < target) {
return 0;
}
long denominator = 1;
int total = 0;
for (int occur : count) {
if (occur > 0) {
total += occur;
denominator *= (factorial(occur));
}
}
return (int)(factorial(total) / denominator);
}

private long factorial(int n) {
return factorial(n, 1L);
}

private long factorial(int n, long m) {
return n == 1 ? m : factorial(n - 1, m * n);
}
}
``````

• @dachuan.huang

• DP is required in this problem for performance
• your solution is rather a mess, try to make it clean and tidy
``````class Solution {
private:
int arr[10000]{0};
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.empty() || target<0) return 0;
if(target == 0) return 1;
if(arr[target]) return arr[target];
long count = 0;
for(int i = 0; i < nums.size(); ++i)
count += combinationSum4(nums, target-nums[i]);
return arr[target] = count;
}
};
``````

• @LHearen I am using the combinatorial formula: (a1 + a2 + a3 .. + ak) ! / a1! * a2! * ... * ak!

Right. the code looks lengthy.

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