Can we use knapsack + recursion for leetcode combination sum 4

Question

For https://leetcode.com/problems/partition-equal-subset-sum

var canPartition = function(ns) {
    // sum
    const s = ns.reduce((acc, t) => acc+t, 0);
    
    // half
    condi = s % 2 === 0 ? true : false
    if(condi === false) return false;
    
    // sort
    ns.sort((a, b) => a-b);
    const sum = s/2;
    
    // memo_2D
    const dp = [];
    for(let i=0; i<ns.length; ++i) {
        dp[i] = Array(sum+1).fill(null);
    }

    return recur(ns, 0, sum, dp);
};


var recur = function(ns, i, tar, dp) {
    // ind guard
    if(i >= ns.length) return false;
    // equal
    if(tar === 0) return true;
    // over_consume
    if(tar < 0) return false;
    // if top, this catch everything   
    if(dp[i][tar] !== null) return dp[i][tar];
    
    // knapsack recur, memo_2D
    const res = recur(ns, i+1, tar-ns[i], dp) || recur(ns, i+1, tar, dp);

    return dp[i][tar] = res;
}

I can use knapsack (pick this element or not) + recursion. It passes all test cases.

I tried to apply the same method (knapsack + recursion) in the following question.

https://leetcode.com/problems/combination-sum-iv

var combinationSum4 = function(ns) {
    const s = ns.reduce((acc, t) => acc+t, 0);
    ns.sort((a, b) => a-b);
    const sum = s;
    
    // memo_2D
    const dp = [];
    for(let i=0; i<=sum; ++i) {
        dp[i] = Array(ns.length+1).fill(null);
    }

    return recur(ns, 0, sum, dp);
};


var recur = function(ns, i, tar, dp) {  
    if(i >= ns.length) return 0;
    if(tar === 0) return 1;
    if(tar < 0) return 0;
    if(dp[tar][i] !== null) return dp[tar][i];
    
    const res = recur(ns, i+1, tar-ns[i], dp) + recur(ns, i+1, tar, dp);
    return dp[tar][i] = res;
}

The dp 2D array is not filled.

My question:

1. Is it a knapsack problem?
2. Can we use knapsack + recursion to resolve?

Answer 1

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        n=len(nums)
        dp=[[0]*(target+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0]=1
        for i in range(1,n+1):
            for j in range(1,target+1):
                if nums[i-1]<=target:
                    dp[i][j]=dp[i][j-nums[i-1]]+dp[i-1][j]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[n][target]

How about this where I used tabulation approach . With slight variation , I was able to use this approach in coin change problem but its not working here apparently

Answer 2

I think the second problem is more of a coin change type DP problem (rather knapsack + recursion one). The following code solves the problem:

int combinationSum4(vector<int>& nums, int target) {
    vector<int> dp(target+1, 0);
    dp[0] = 1;
    int sz = nums.size();

    for(int i=1; i<=target; i+=1) {
        for(int j=0; j<sz; j+=1) {
            if(i >= nums[j]) dp[i] += dp[i - nums[j]];
        }
    }

    return dp[target];
}