Combination Sum 4

Problem Statement

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3 Output: 0

Constraints:

1 ⇐ nums.length ⇐ 200 1 ⇐ nums[i] ⇐ 1000 All the elements of nums are unique. 1 ⇐ target ⇐ 1000

Solution:

 public int backtrack(int index, int[] nums, int target, List<Integer> possAns, int[] dp) {
        if (target == 0) {
            return 1;
        }
        if (index == nums.length) {
            return 0;
        }
        if (dp[target] != -1) {
            return dp[target];
        }
        
        // Initialize count
        int count = 0;
        
        // Iterate over each number from the start
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= target) {
                possAns.add(nums[i]);
                count += backtrack(0, nums, target - nums[i], possAns, dp);
                possAns.remove(possAns.size() - 1);
            }
        }
        
        dp[target] = count;
        return dp[target];
    }
    
    public int combinationSum4(int[] nums, int target) {
        List<Integer> possAns = new ArrayList<>();
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        
        return backtrack(0, nums, target, possAns, dp);
    }