Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note: Each of the array element will not exceed 100. The array size will not exceed 200. Example 1:

Example 2:

http://www.cnblogs.com/grandyang/p/5951422.html 這道題給了我們一個數組，問我們這個數組能不能分成兩個非空子集合，使得兩個子集合的元素之和相同。那么我們想，原數組所有數字和一定是偶數，不然根本無法拆成兩個和相同的子集合，那么我們只需要算出原數組的數字之和，然后除以2，就是我們的target，那么問題就轉換為能不能找到一個非空子集合，使得其數字之和為target。開始我想的是遍歷所有子集合，算和，但是這種方法無法通過OJ的大數據集合。于是乎，動態規劃DP就是我們的不二之選。我們定義一個一維的dp數組，其中dp[i]表示數字i是否是原數組的任意個子集合之和，那么我們我們最后只需要返回dp[target]就行了。我們初始化dp[0]為true，由于題目中限制了所有數字為正數，那么我們就不用擔心會出現和為0或者負數的情況。那么關鍵問題就是要找出遞歸公式了，我們需要遍歷原數組中的數字，對于遍歷到的每個數字nums[i]，我們需要更新我們的dp數組，要更新[nums[i], target]之間的值，那么對于這個區間中的任意一個數字j，如果dp[j - nums[j]]為true的話，那么dp[j]就一定為true，于是地推公式如下：

dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)

有了遞推公式，那么我們就可以寫出代碼如下：

這道題還可以用bitset來做，感覺也十分的巧妙，bisets的大小設為5001，為啥呢，因為題目中說了數組的長度和每個數字的大小都不會超過100，那么最大的和為10000，那么一半就是5000，前面再加上個0，就是5001了。我們初始化把最低位賦值為1，然后我們算出數組之和，然后我們遍歷數字，對于遍歷到的數字num，我們把bits向左平移num位，然后再或上原來的bits，這樣所有的可能出現的和位置上都為1。舉個例子來說吧，比如對于數組[2,3]來說，初始化bits為1，然后對于數字2，bits變為101，我們可以看出來bits[2]標記為了1，然后遍歷到3，bits變為了101101，我們看到bits[5],bits[3],bits[2]都分別為1了，正好代表了可能的和2，3，5，這樣我們遍歷玩整個數組后，去看bits[sum >> 1]是否為1即可，參見代碼如下：

解法二：