3ms C++ DFS with prune


  • 0
    B

    DFS is still a good solution after test set is updated, as long as we prune it.

    #include <numeric>
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = std::accumulate(nums.begin(), nums.end(), 0);
            // If sum is odd, cannot partition
            if (sum & 1) return false;
            bucketSort(nums);
            return dfs(nums, 0, sum >> 1);
        }
        
        void bucketSort(vector<int>& nums) {
            vector<int> buckets(101, 0);
            for (int num : nums) {
                buckets[num]++;
            }
            int index = 0;
            for (int i = 100; i >= 1; --i) {
                for (int j = 0; j < buckets[i]; ++j) {
                    nums[index++] = i;
                }
            }
        }
        
        bool dfs(const vector<int>& nums, int start, int target) {
            if (target == 0) {
                return true;
            } else if (start >= nums.size()) {
                return false;
            } else {
                // prune, if sum of remaining numbers is less than target, return false
                int sum = std::accumulate(nums.begin() + start, nums.end(), 0);
                if (sum == target) return true;
                else if (sum < target) return false;
                
                for (int i = start; i < nums.size(); ++i) {
                    if (nums[i] > target) continue;
                    if (dfs(nums, i + 1, target - nums[i])) return true;
                }
                
                return false;
            }
        }
    };
    

Log in to reply
 

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