416. 分割等和子集
給定一個(gè)只包含正整數(shù)的非空數(shù)組。是否可以將這個(gè)數(shù)組分割成兩個(gè)子集崎场，使得兩個(gè)子集的元素和相等。
輸入: [1, 5, 11, 5]
輸出: true
解釋: 數(shù)組可以分割成 [1, 5, 5] 和 [11].
這道題可以用01背包來求解享言，也就是數(shù)組中的數(shù)能否能裝下sum/2的包市殷，即dp[sum/2]是否為true.
class Solution {
public:
bool canPartition(vector<int>& nums) {
const int sum = std::accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
vector<int> dp(sum + 1, 0);
dp[0] = 1;
for (const int num : nums) {
for (int i = sum/2; i >= 0; --i)
if (dp[i]) dp[i+num] = 1;
if (dp[sum / 2]) return true;
}
return false;
}
};
在評(píng)論區(qū)看到一個(gè)用bitset來做的，雖然還不太懂矮湘，但還是記錄下來回頭來看再做補(bǔ)充斟冕。
class Solution {
public:
bool canPartition(vector<int>& nums) {
if(nums.size()<2) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum&1) return false;
bitset<10001> bits(1);
for (auto n : nums) bits |= bits << n;
return bits[sum >> 1];
}
}
377. 組合總和 Ⅳ
給定一個(gè)由正整數(shù)組成且不存在重復(fù)數(shù)字的數(shù)組，找出和為給定目標(biāo)正整數(shù)的組合的個(gè)數(shù)缅阳。
nums = [1, 2, 3]
target = 4
所有可能的組合為：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
這是一道涉及順序的完全背包磕蛇。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.empty()) return 0;
vector<unsigned long long> dp(target+1,0);//用int會(huì)溢出
dp[0]=1;
for(int i=1;i<=target;i++){
for(auto num:nums){
if(i>=num) dp[i]+=dp[i-num];
}
}
return dp.back();
}
};
