# Concise C++ Solution summary with DFS, DP, BIT

1. 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);
}
};
``````
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];
}
``````
1. 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];
}
``````

• Hi I got the same idea as yours:

``````class Solution {
public:
bool find(vector<int> & nums, int target, int start) {
if (target == 0) {
return true;
}
else {
for (int i = start; i < nums.size(); i++) {
if (nums[i] <= target) {
if(find(nums, target-nums[i], i+1)) {
return true;
}
}
}
return false;
}
}
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 == 1) {
return false;
}
else {
return find(nums, sum/2, 0);
}
}
};
``````

Just wondering have you or anyone tried to analyze the time complexity of this? I think it should be O(n!). Please correct me if I'm wrong.

• anyone tried to analyze the time complexity of this? I think it should be O(n!). Please correct me if I'm wrong.

I think so, but I saw someone says it is O(n^2) in discussion without explanation.
Some test cases were added to this problem. So now this way is TLE.
I need figure out a DP solution

• @zyoppy008 Yeah, I got TLE as well with the new test case, which makes sense....

• @zyoppy008 hey brother, you are so smart. love you

• If you sort the array first. DFS larger num first, you can still pass the OJ.

• dfs can still pass OJ if you add some improving tricks like:

1. Sort the array first, and whenever you find your sum bigger than target, just return
2. Using memorization, whenever you meet the same "current sum" + "current position" combo as before, just return
3. Set a global bool var or pass it as reference, every time come to a new call of helper function, check that var first, if it's true already , no need to travel further.

• @zyoppy008 I think the time complexity is O(2^n). Since in DFS, there are two situations for each element: selected or not. Correct me if it is wrong.

• @Dongwei.Wang I have one currently working dfs code, 3 ms. I have reported to the admin.

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i:nums) sum += i;
if (sum&1) return false;
sum /= 2;
sort(nums.rbegin(), nums.rend());
return helper(nums, 1, nums[0], sum);
}
private:
bool helper(vector<int>& nums, int cur, int tot, int tar) {
for (int i = cur; i < nums.size(); i++) {
if (tot+nums[i] <= tar && helper(nums, i+1, tot+nums[i], tar))
return true;
}
}
};
``````

• Here's AC DFS+memorization (about 70ms), same algorithm as original post, except adding an unordered_set to memorize failed paths.

``````class Solution {
private:
unordered_set<string> visited;
bool dfs(vector<int>& nums, int idx, int target) {
if (target<0) return false;
if (target==0) return true;

if (visited.count(to_string(idx)+'-'+to_string(target))) return false;

for (int i=idx; i<nums.size(); i++) {
if (dfs(nums,i+1,target-nums[i])) return true;
}

visited.insert(to_string(idx)+'-'+to_string(target));
return false;
}
public:
bool canPartition(vector<int>& nums) {
int sum=accumulate(nums.begin(),nums.end(),0);
return sum%2==0 && dfs(nums,0,sum/2);
}
};
``````

Looking at @zestypanda's solution, as well as other posts, I think sorting + aggressive trimming can be extremely fast. I added 2 lines to the original post's DFS solution to accomplish the 3ms run time reported by others.

``````class Solution {
private:
bool dfs(vector<int>& nums, int idx, int target) {
if (target<0) return false;
if (target==0) return true;
for (int i=idx; i<nums.size(); i++) {
if (target-nums[i]<0) break; // trims the dfs since we already sorted nums
if (dfs(nums,i+1,target-nums[i])) return true;
}
return false;
}
public:
bool canPartition(vector<int>& nums) {
int sum=accumulate(nums.begin(),nums.end(),0);
sort(nums.rbegin(),nums.rend()); // sort the nums
return sum%2==0 && dfs(nums,0,sum/2);
}
};
``````

• @zyoppy008 Hi, here is my passed DFS solution, just to maintain some extra information: C++ DFS beating 95.17% (3ms)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.