Блог

Для 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;
}
 

Я могу использовать рюкзак (выбрать этот элемент или нет) рекурсия. Он проходит все тестовые случаи.

Я попытался применить тот же метод (рюкзак рекурсия) в следующем вопросе.

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

Массив dp 2D не заполнен.

Мой вопрос:

1. Это проблема с рюкзаком?
2. Можем ли мы использовать рюкзак рекурсию для решения?

Я думаю, что вторая проблема больше связана с проблемой DP типа размена монет (скорее knapsack recursion одна). Следующий код решает проблему:

 int combinationSum4(vector<int>amp; 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];
}