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


  • 12
    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];
    }
    

  • 0
    M

    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.


  • 1

    @mugua-stolaf said in 6 lines Concise DFS C++ Solution:

    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


  • 0
    M

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


  • 0
    S

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


  • 0
    L

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


  • 1
    J

    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.

  • 0
    D

    @JadenPan Do you have an AC code for your idea?


  • 0
    D

    @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.


  • 0
    Z

    @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) {
            if (cur == nums.size()) return tot == tar;
            for (int i = cur; i < nums.size(); i++) {
                if (tot+nums[i] <= tar && helper(nums, i+1, tot+nums[i], tar))
                    return true;
            }
            return tot == tar;
        }
    };
    

Log in to reply
 

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