1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
public:
    bool canPartition(vector<int>::iterator begin, vector<int>::iterator end, int sum) {
        if (begin == end)
            return false;
        if (*begin == sum)
            return true;
        if (*begin > sum)
            return false;
        return canPartition(begin + 1, end, sum - *begin) || canPartition(begin + 1, end, sum);
    }

    bool canPartition(vector<int>& nums) {
        auto it = nums.begin();
        int sum = 0;
        for (; it < nums.end(); it++)
            sum += *it;
        
        if (sum & 1)
            return false;
            
        
        it      = nums.begin();
        auto end = nums.end();
        return canPartition(it, end, sum >> 1);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        auto it = nums.begin();
        int sum = 0;
        for (; it < nums.end(); it++)
            sum += *it;
        if (sum & 1)
            return false;
        
        bool** b = new bool*[nums.size() + 1];
        for (int i = 0; i <= nums.size(); i++) {
            b[i] = new bool[sum / 2 + 1];
        }

        
        b[0][0] = true;
        for (int j = 1; j <= sum / 2; j++) {
            b[0][j] = false;
        }

        
        for (int i = 1; i <= nums.size(); i++) {
            
            for (int j = 0; j <= sum / 2; j++)
                b[i][j] = b[i - 1][j];

            
            for (int j = 0; j <= sum / 2; j++)
                if (b[i - 1][j] && j + nums[i - 1] <= sum / 2)
                    b[i][j + nums[i - 1]] = true;

            
            if (b[i][sum / 2])
                return true;
        }
        
        return false;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        auto it = nums.begin();
        int sum = 0;
        for (; it < nums.end(); it++)
            sum += *it;
        if (sum & 1)
            return false;
        
        bool* boolarray = new bool[sum + 1]();
        sum >>= 1;
        for (it = nums.begin(); it < nums.end(); it++) {
            
            for (int j = sum; j >= 0; j--)
                if (boolarray[j])
                    boolarray[j + *it] = 1;
            
            boolarray[*it] = 1;
            
            if (boolarray[sum])
                return true;
        }
        
        return false;
    }
};