Two C++ Solutions: DFS and DP


  • 1

    Solution 1 : DFS, O(2^N), TLE now due to new test cases added

    class Solution {
    public:
        bool dfs(vector<int>& nums, int cur, int sum) {
            if (sum == 0) return true;
            if (sum < 0) return false;
            for (int i = cur; i < (int)nums.size(); ++i)
                if (dfs(nums, i+1, sum-nums[i])) return true;
            return false;
        }
        bool canPartition(vector<int>& nums) {
            long long sum = accumulate(nums.begin(), nums.end(), 0);
            return sum & 1 ? false : dfs(nums, 0, sum/2);
        }
    };
    

    Solution 2 : DP, O(M*N) (M is half of array sum), 251ms

    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            long long sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum & 1) return false;
            sum /= 2;
            vector<int> dp(sum+1, 0);
            for (int i = 1; i <= sum; ++i) dp[i] = INT_MIN;
            for (int i = 0; i < (int)nums.size(); ++i) {
                for (int j = sum; j >= nums[i]; --j)
                    dp[j] = max(dp[j-nums[i]]+1, dp[j]);
            }
            return dp[sum] > 0;
        }
    };
    

    BTW, DP solution can be seen as the variation of the well-known '01 Knapsack Problem'.


  • 0
    Y

    You sure DFS is N^2 ?, for each n, you have a for loop, each sub-problem in the for loop will lead to another for loop recursively.


  • 0
    This post is deleted!

  • 0

    @vesion
    Hi vesion, test cases for these problem was designed too weak. I'll add more test cases in minutes. Thanks for your feedback.


  • 0

    @vesion
    Hi, can you explain why DFS is N^2 ?
    Thanks


  • 0

    @zyoppy008
    I'm so sorry for my wrong answer above on the time complexity of DFS solution.
    It's time complexity is exponential, O(2^n) specifically. Because the progress is pretty much the same with the combination problem, so it is also exponential.


  • 0

    @ywh1988
    I'm so sorry for my wrong answer, it's O(2^n). Apologize again :)


Log in to reply
 

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