組合數(shù)問(wèn)題

我們思考一下，如果要把數(shù)組分割成兩個(gè)子集，并且兩個(gè)子集的元素和相等，是否等價(jià)于在數(shù)組中尋找若干個(gè)數(shù)使之和等于所有數(shù)的一半？是的！

因此我們可以想到，兩種方式：

①回溯的方式找到target，但是回溯是階乘級(jí)別的算法，這里會(huì)超時(shí)。

②從前往后遍歷，形象說(shuō)明：定義n個(gè)集合dp[i]，dp[i]表示前i個(gè)數(shù)的可能組合值，則有dp[i]={dp[i-1],dp[i-1]+i}，dp[i-1]+i指的是i加上dp[i-1]中的所有元素得到的集合。同時(shí)由于長(zhǎng)度最長(zhǎng)200，數(shù)值最大為100，因此數(shù)的范圍最大為1<=i<=20000，因此最多只有20000個(gè)不同的數(shù)。因此dp最大為2W個(gè)數(shù)！所以我們可以用集合實(shí)現(xiàn)，并且時(shí)間復(fù)雜度滿(mǎn)足要求O(nums.length*nums.length*max(nums[i]))！

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;//只有偶數(shù)總和可以
        sum>>=1;
        unordered_set<int> Set;
        vector<int> temp;
        for(auto &i:nums){
            if(i==sum) return true;
            for(auto it=Set.cbegin();it!=Set.cend();++it){
                int cur=*it+i;
                if(cur==sum) return true;
                if(cur<sum) temp.emplace_back(cur);//＞sum的沒(méi)意義
            }
            for(auto & j:temp) Set.insert(j);
            temp.clear();
            Set.insert(i);
        }
        return false;
    }
};

遇到的問(wèn)題：

? ? ? ? 在循環(huán)遍歷的過(guò)程中往容器中插入元素會(huì)導(dǎo)致容器迭代器end()和size()，時(shí)刻發(fā)生變化。與此同時(shí)，有的容器比如vector和string，往后面增加元素超過(guò)容量capacity可能會(huì)導(dǎo)致拷貝，從而整個(gè)迭代器失效。因此！在使用循環(huán)并且需要添加元素時(shí)，想使用迭代器需要額外注意！

比如本題是先將所需增加的放入到一個(gè)vector中的。

我們不能企圖使用臨時(shí)“指針”迭代器i=end()，然后遍歷到it!=i，這是錯(cuò)誤的！因?yàn)閑nd()可能失效，而不是end()當(dāng)時(shí)指向的位置。以下是C++ prime中特地提到的（這么小，但又特別災(zāi)難的坑被遇到了）

int tmp=Set.size();
for(auto it=Set.cbegin();tmp!=0;++it,--tmp){ 
    int cur=*it+i;
    if(cur==sum) return true;
    temp.emplace_back(cur);
    Set.insert(cur);
}

這樣做仍然是錯(cuò)誤的，實(shí)際上我們?cè)谕琼樞蛉萜髦胁迦朐貢r(shí)，容器的數(shù)據(jù)結(jié)構(gòu)會(huì)發(fā)生變化，因此導(dǎo)致++it可能并非按照原來(lái)的想法遍歷，所以是錯(cuò)誤的！

唯一正確且安全的方式是，如果需要在遍歷的時(shí)候同時(shí)添加元素，最好不要使用迭代器！迭代器可以很好的遍歷元素或者按迭代器范圍賦值。但是邊添加邊遍歷問(wèn)題非常大。

因此對(duì)于無(wú)序容器只能使用迭代器的情況下，使用臨時(shí)容器存儲(chǔ)是非常必要的；對(duì)于順序容器可以使用下標(biāo)的情況下，使用下標(biāo)更好。

動(dòng)態(tài)規(guī)劃

????????這道題實(shí)際上和0-1背包問(wèn)題很像，即從n個(gè)物品中拿出一部分使得其值剛好等于target。意識(shí)到這一點(diǎn)我們可以定義動(dòng)態(tài)轉(zhuǎn)移方程：

dp[i][k]=max(dp[i-1][k-nums[i]],dp[i-1][k]);

dp[0][nums[0]]=1;

//dp[i][k]表示拿前i個(gè)物品是否可以達(dá)到重量k。

????????這實(shí)際上和方法一組合數(shù)問(wèn)題是異曲同工的，方法一使用集合實(shí)現(xiàn)，那么如果方法一使用的是數(shù)組實(shí)現(xiàn)呢？那么數(shù)組中標(biāo)記為1的實(shí)際上就是方法二的狀態(tài)了！

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;
        sum>>=1;
        vector<vector<int>> dp(nums.size(),vector<int>(sum+1,0));//超過(guò)sum實(shí)際上就不用看了
        if(nums[0]<=sum)
            dp[0][nums[0]]=1;
        for(int i=1;i<nums.size();++i){
            for(int j=1;j<=sum;++j){
                dp[i][j]=dp[i-1][j];
                if(j-nums[i]>=0)
                    dp[i][j]=max(dp[i-1][j-nums[i]],dp[i-1][j]);
            }
            if(nums[i]<=sum)
                dp[i][nums[i]]=1;
        }
        return dp[nums.size()-1][sum];
    }
};

由于只用到前面的值，很顯然我們可以降維優(yōu)化。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-860549.html

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;
        for(auto &i:nums) sum+=i;
        if(sum&1||nums.size()==1) return false;
        sum>>=1;
        vector<int> dp(sum+1,0);//超過(guò)sum實(shí)際上就不用看了
        if(nums[0]<=sum)
            dp[nums[0]]=1;
        for(int i=1;i<nums.size();++i){
            for(int j=sum;j>=nums[i];--j){
                dp[j]=max(dp[j],dp[j-nums[i]]);
            }
        }
        return dp[sum];
    }
};

到了這里，關(guān)于力扣hot100：416.分割等和子集（組合/動(dòng)態(tài)規(guī)劃/STL問(wèn)題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！