- DFS solution:

```
class Solution {
public:
bool backtrack(vector<int>& nums, int start, int target) {
if (target <= 0) return target == 0;
for (int i = start; i < nums.size(); i++)
if (backtrack(nums, i + 1, target - nums[i])) return true;
return false;
}
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
return !(sum & 1) && backtrack(nums, 0, sum >> 1);
}
};
```

- DFS can't pass the OJ, as more test cases are added. So here comes a DP solution based on @Hermits solution

```
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0), target = sum >> 1;
if (sum & 1) return false;
vector<int> dp(target + 1, 0);
dp[0] = 1;
for(auto num : nums)
for(int i = target; i >= num; i--)
dp[i] = dp[i] || dp[i - num];
return dp[target];
}
```

- A very fast and cool Bit solution by @alvin-777 solution

```
bool canPartition(vector<int>& nums) {
bitset<5001> bits(1);
int sum = accumulate(nums.begin(), nums.end(), 0);
for (auto n : nums) bits |= bits << n;
return !(sum & 1) && bits[sum >> 1];
}
```