724. Minimum Partition

Code(Language:C++) (Judger:cloudjudge-cluster-4)

转成背包问题

class Solution {
public:
    /**
     * @param nums: the given array
     * @return: the minimum difference between their sums 
     */
    int findMin(vector<int> &nums) {
        // write your code here
        int sum = 0; 
        for(int i = 0; i < nums.size(); i++){
            sum += nums[i]; 
        }
        int halfNear = backPack(sum / 2, nums); 
        return abs(sum - halfNear - halfNear); 
    }
   int backPack(int m, vector<int> A) {
        // write your code here
        vector<int> res(m + 1);
        res[0] = 1; 
        
        for (int j = 0; j < A.size(); j++) {
            for (int i = m; i >= A[j]; i--) {
                res[i] = res[i] || res[i - A[j]];
            }
        }
        
        for (int i = m; i >= 0; i--) {
            if (res[i]) {
                return i; 
            }
        }
    }
};