Correct numerically but overflow solution (because of factorial)


  • 0
    D
    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);
        }
    }
    

  • 0

    @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;
        }
    };
    

  • 0
    D

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

    Right. the code looks lengthy.


Log in to reply
 

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