C++ 5-line DFS solution with detailed explanation


  • 0

    Key observation: Such partition exists if and only if

    • The array sum sum is even;
    • There is a subset with sum equal to target sum/2.

    For sub array up to position i against target t, the DFS algorithm will be straightforward to check

    1. if including current value nums[i] in the subset, check sub array up to position i-1 against target t-nums[i];
    2. otherwise, check sub array up to position i-1 against target t.

    And we claim the desired partition exists if either 1 or 2 holds.

    Note: Inspired by @YJL1228 , for DFS, pre-process array nums with sorting is necessary since the dfs routine needs to return by traversing as fewer numbers as possible. So traversing larger numbers first will speed up to decide whether a desired subsum exists, i.e., if you want to fail, make sure to fail quickly.

        bool canPartition(vector<int>& nums) {
          int sum = accumulate(nums.begin(), nums.end(), 0);
          sort(nums.begin(), nums.end()); rend = nums.rend();
          return !(sum%2) && dfs(nums.rbegin(), sum/2);
        }
        // if sub array up to position `i` has a subset with sum equal to target `t`
        bool dfs(vector<int>::reverse_iterator i, int t) {
          return (i == rend || t <= 0)? false : !t || t == *i || dfs(i+1, t-*i) || dfs(i+1, t);
        }
        
        vector<int>::reverse_iterator rend;
    

Log in to reply
 

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