Problem statement:

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:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]Output: trueExplanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]Output: falseExplanation: The array cannot be partitioned into equal sum subsets.

Solution: DFS with return value(TLE).

This is problem can be solved by DFS with or without a return value. I choose a the DFS template with a bool return value. It returns true once we find a subset. 

Before the DFS, I sort the array in ascending order first.

In each DFS level, ignore the duplicated value.

One cur_sum < 0, return false. 

cur_sum == 0, return true;

cur_sum ---> continue on DFS search.

However, it is a TLE solution, can not pass OJ. 

Since there are two situations for each element: selected or not. Time complexity is O(2^n).

class Solution {public:    bool canPartition(vector<int>& nums) {        sort(nums.begin(), nums.end());         int sum = accumulate(nums.begin(), nums.end(), 0);        return !(sum & 1) && can_partition_dfs(nums, sum / 2, 0);    }    bool can_partition_dfs(vector<int>& nums, int cur_sum, int idx){        if(cur_sum < 0){            return cur_sum == 0;        }        int can_partition = false;        for(int i = idx; i < nums.size(); i++){            can_partition |= can_partition_dfs(nums, cur_sum - nums[i], i + 1);            while(i + 1 < nums.size() && nums[i] == nums[i + 1]){                i++;            }        }        return can_partition;    }};

416. Partition Equal Subset Sum