Java DFS Solution with Explanation


  • 42

    According to https://en.wikipedia.org/wiki/Partition_problem, the partition problem (or number partitioning) is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. The partition problem is NP-complete.

    When I trying to think how to apply dynamic programming solution of above problem to this one (difference is divid S into 4 subsets), I took another look at the constraints of the problem:
    The length sum of the given matchsticks is in the range of 0 to 10^9.
    The length of the given matchstick array will not exceed 15.

    Sounds like the input will not be very large... Then why not just do DFS? In fact, DFS solution passed judges.

    Anyone solved this problem by using DP? Please let me know :)

    public class Solution {
        public boolean makesquare(int[] nums) {
        	if (nums == null || nums.length < 4) return false;
            int sum = 0;
            for (int num : nums) sum += num;
            if (sum % 4 != 0) return false;
            
        	return dfs(nums, new int[4], 0, sum / 4);
        }
        
        private boolean dfs(int[] nums, int[] sums, int index, int target) {
        	if (index == nums.length) {
        	    if (sums[0] == target && sums[1] == target && sums[2] == target) {
        		return true;
        	    }
        	    return false;
        	}
        	
        	for (int i = 0; i < 4; i++) {
        	    if (sums[i] + nums[index] > target) continue;
        	    sums[i] += nums[index];
                if (dfs(nums, sums, index + 1, target)) return true;
        	    sums[i] -= nums[index];
        	}
        	
        	return false;
        }
    }
    

    Updates on 12/19/2016 Thanks @benjamin19890721 for pointing out a very good optimization: Sorting the input array DESC will make the DFS process run much faster. Reason behind this is we always try to put the next matchstick in the first subset. If there is no solution, trying a longer matchstick first will get to negative conclusion earlier. Following is the updated code. Runtime is improved from more than 1000ms to around 40ms. A big improvement.

    public class Solution {
        public boolean makesquare(int[] nums) {
        	if (nums == null || nums.length < 4) return false;
            int sum = 0;
            for (int num : nums) sum += num;
            if (sum % 4 != 0) return false;
            
            Arrays.sort(nums);
            reverse(nums);
            
        	return dfs(nums, new int[4], 0, sum / 4);
        }
        
        private boolean dfs(int[] nums, int[] sums, int index, int target) {
        	if (index == nums.length) {
        	    if (sums[0] == target && sums[1] == target && sums[2] == target) {
        		return true;
        	    }
        	    return false;
        	}
        	
        	for (int i = 0; i < 4; i++) {
        	    if (sums[i] + nums[index] > target) continue;
        	    sums[i] += nums[index];
                if (dfs(nums, sums, index + 1, target)) return true;
        	    sums[i] -= nums[index];
        	}
        	
        	return false;
        }
        
        private void reverse(int[] nums) {
            int i = 0, j = nums.length - 1;
            while (i < j) {
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++; j--;
            }
        }
    }
    

  • 0
    F

    very concise DFS solution,thx!


  • 0
    Z

    My submission in Python of exactly the same idea will get TLE.

    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            if len(nums) < 4:
                return False
            target = int(sum(nums) / 4)
            return self.helper(nums, 0, 0, 0, 0, 0, target)
            
        def helper(self, nums, a, b, c, d, i, target):
            if a > target or b > target or c > target or d > target:
                return False
            if i == len(nums):
                return a == b == c == d == target
            s = nums[i]
            if self.helper(nums, a+s, b, c, d, i+1, target) or self.helper(nums, a, b+s, c, d, i+1, target) or self.helper(nums, a, b, c+s, d, i+1, target) or self.helper(nums, a, b, c, d+s, i+1, target):
                return True
            return False
    

  • 0
    Z

    @shawngao said in Java DFS Solution with Explanation:

    length

    Hi can you re-submit your code and make sure it's not TLE? Because I tried the same version in C++ and got TLE (138 / 173 test cases passed, so I believe the correctness is OK). Thanks!


  • 0

    @Zhuzeng Just submitted again, still accepted...

    173 / 173 test cases passed.
    Status: Accepted
    Runtime: 1349 ms
    Submitted: 0 minutes ago


  • 0
    K

    By inlining array, it passed in C++ :(

    // passed (1892 ms)
    bool dfs2(vector<int>& nums, int k, int l1, int l2, int l3, int l4) {
            if (k==nums.size()) {
                return l1==0&&l2==0&&l3==0&&l4==0;
            }
            
            int l = nums[k];
            
            if (l<=l1&&dfs2(nums, k+1, l1-l,l2,l3,l4)) return true;
            if (l<=l2&&dfs2(nums, k+1, l1,l2-l,l3,l4)) return true;
            if (l<=l3&&dfs2(nums, k+1, l1,l2,l3-l,l4)) return true;
            if (l<=l4&&dfs2(nums, k+1, l1,l2,l3,l4-l)) return true;
            
            return false;
    }
    
    // 140 / 173 test cases passed (TLE)
    bool dfs(vector<int>& nums, int k, vector<int>& ls) {
            if (k==nums.size()) {
                for(int l: ls) {
                    if (l!=0) return false;
                }
                return true;
            }
            
            int l = nums[k];
            
            for(int i=0; i<4; i++) {
                if (l>ls[i]) continue;
                ls[i]-=l;
                if (dfs(nums, k+1, ls)) return true;
                ls[i]+=l;
            }
            
            return false;
    }
    
    
    

  • 0
    H

    It can be faster by avoiding calling dfs for sums[j] where j > i and sums[j] == sums[i].
    I had same logic as yours in C# and hit TLE, and passed the test after adding that optimization.

    public class Solution {
        public bool Makesquare(int[] nums) {
            if (nums.Length == 0) {
                return false;
            }
            
            int sum = 0;
            for (int i=0; i<nums.Length; i++) {
                sum += nums[i];
            }
            
            if (sum % 4 != 0) {
                return false;
            }
            
            int edge = sum / 4;
            return MakeSome(nums, 0, new[] {edge, edge, edge, edge});
        }
        
        private bool MakeSome(int[] nums, int start, int[] edges) {
            if (start == nums.Length) {
                for(int e=0; e<edges.Length; e++) {
                    if (edges[e] != 0) {
                        return false;
                    }
                }
                
                return true;
            }
            
            int n = nums[start];
            HashSet<int> tried = new HashSet<int>();
            for(int i=0; i<edges.Length; i++) {
                if (edges[i] >= n && !tried.Contains(edges[i])) {
                    edges[i] -= n;
                    if (MakeSome(nums, start+1, edges)) {
                        return true;
                    }
                    edges[i] += n;
                    tried.Add(edges[i]);
                }
            }
            
            return false;
        }
    }
    

  • 0
    L
    This post is deleted!

  • 10

    @zizhengwu-bot You can make some minor adjustment to prune the search space (or tree).

    For example, you can sort nums by descending order. In dfs, the condition which determine whether dfs should keep exploring is this if side + nums[index] > length: continue. When nums is sorted reversely, this condition will be hit sooner.

    I also find this algorithm work pretty good when nums can be divided into 4 subset whose have equal sums.

    For example, this is still pretty fast

    Solution().makesquare([1,2,3,4]*128)
    

    It chokes a bit when nums cannot be divided into 4 such subset as it has to explore the whole tree.

    There are some constant time improvement that we can do. For example, assume the input is [4,3,3,3,3], assume we try put 4 and 3 into the sides[0] and there is no feasible solutions, there are no need to put them into sides[1], sides[2] or sides[3] (Note: I didn't implement this)

    class Solution(object):
        def makesquare(self, nums):
            """
            :type nums: List[int]
            :rtype: bool
            """
            # Easier to reach the leaf when we have a reversed sorted `nums`
            nums = sorted(nums, reverse=True)
            
            total_length = sum(nums)
            length = sum(nums) / 4 
            
            # Eliminate some obious case
            if len(nums) < 4 or total_length % 4 != 0 or any(num > length for num in nums):
                return False
            
            return self.dfs(nums, [0,0,0,0], 0, length)
            
        def dfs(self, nums, sides, index, length):
            if len(nums) == index:
                return all(side == length for side in sides)
                
            for i, side in enumerate(sides):
                if side + nums[index] > length: continue
                sides[i] += nums[index]
                if self.dfs(nums, sides, index+1, length): return True
                sides[i] -= nums[index]
            
            return False
    

  • 0
    H

    @benjamin19890721 sort in descending is critical and make big difference!

    C++ version with sort() 143ms. Without sorting, it hits TLE

    class Solution {
    public:
        bool makesquare(vector<int>& nums) {
            int n = nums.size();
            if (n < 4) return false;
            int sum = 0;
            for (auto x : nums) sum += x;
            if (sum % 4) return false;
            int edge = sum / 4;
            sort(nums.begin(), nums.end(), greater<int>());
            if (nums[0] > edge) return false;
            vector<int> edges(4);
            return dfs(nums, 0, edges, edge);
        }
        
        bool dfs(vector<int>& nums, int idx, vector<int>& v, int len) {
            if (idx == nums.size()) {
                return (v[0] == len && v[1] == len && v[2] == len);
            }
            for (int i = 0; i < 4; i++) {
                if (v[i] + nums[idx] <= len) {
                    v[i] += nums[idx];
                    if (dfs(nums, idx+1, v, len)) return true;
                    v[i] -= nums[idx];
                }
            }
            return false;
        }
    };
    

  • 0

    @benjamin19890721 Your optimization really improves runtime quite a lot. Thanks!


  • 0
    R

    What is the time complexity of these two methods: with and without optimization?


  • 0

    @renwoxing I don't think the optimization changes the worst run time complexity. I did a rough math that the worst run time complexity is n! / ( 4 * (n / 4)! )


  • 0
    R

    @shawngao can you explain how to calculate the time complexity? If it is O(n!), it is a "permutation" problem instead of a "subset" problem. Generally a "subset" problem is O(2^n).


  • 2

    @shawngao @renwoxing said in Java DFS Solution with Explanation:

    @shawngao can you explain how to calculate the time complexity? If it is O(n!), it is a "permutation" problem instead of a "subset" problem. Generally a "subset" problem is O(2^n).

    This is actually a subset partitioning problem.

    In the DSF process, from initial sum set (sum/4, sum/4, sum/4, sum/4), the worst case is you can remove nums[i] from any one of the 4 sums (without considering duplicates). So when DSF is done by removing all nums[i] to achieve (0,0,0,0), the values removed from each of the 4 sums form a subset Sk=1:4 of { nums[i=1:N] }, and the union of all Sk=1:4 is { nums[i=1:N] }. So the problem becomes:

    • Given N objects, how many ways can you partition then into 4 subsets with each size Nk=1:4? (Σk=1:4Nk = N)

    Well, the answer is N!/(N1!N2!N3!N4!). Note that for fixed N, the denominator achieves minimum if all Nk=1:4 are identical, so the worse case is

    • N!/(N1!N2!N3!N4!) ≤ N!/(N/4)!4.

    To be straightforward, since this is a NPC problem, the brute force way to directly group N matchsticks into 4 groups is the same number above. However, some of the 4 sides may have same length and 4 side lengths only differ by order which are duplicates, but we consider only roughly the worst case.


  • 0

    @zzg_zzm You are right, it is N!/(N/4)!4 instead of n! / ( 4 * (n / 4)! )


  • 0
    F

    @shawngao Thanks for your solution and thinking process. I have a minor suggestion for you.

    In your dfs part, you could return true when the condition index == num.length met. Actually, you don't need to check if the length == target. Because the dfs will continue and eventually return false for the case we can't construct a valid square (length > target or length < target).


  • 1
    F

    looks like you don't have to reverse the array after sorting it in ascending order, just search from the last element to the first element. Same idea without reversing the array.

    public boolean makesquare(int[] nums) {
        if (nums.length == 0) {
            return (false);
        }
        
        int sum = 0;
        int[] buckets = new int[4];
        
        for (int i : nums) {
            sum += i;
        }
        
        if (sum % 4 != 0) {
            return (false);
        }
        
        Arrays.sort(nums);
        return (dfs(nums, nums.length - 1, buckets, sum / 4));
    }
    
    boolean dfs(int[] nums, int candidate, int[] buckets, int target) {
        if (candidate < 0) {
            return (true);
        }
        
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] += nums[candidate];
            if (buckets[i] <= target) {
                if (dfs(nums, candidate - 1, buckets, target)) {
                    return (true);
                }
            }
            
            buckets[i] -= nums[candidate];
        }
        
        return (false);
    }

  • 0
    A

    said in Java DFS Solution with Explanation:

    public boolean makesquare(int[] nums) {
    if (nums == null || nums.length < 4) return false;
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 4 != 0) return false;

    	return dfs(nums, new int[4], 0, sum / 4);
    }
    
    private boolean dfs(int[] nums, int[] sums, int index, int target) {
    	if (index == nums.length) {
    	    if (sums[0] == target && sums[1] == target && sums[2] == target) {
    		return true;
    	    }
    	    return false;
    	}
    	
    	for (int i = 0; i < 4; i++) {
    	    if (sums[i] + nums[index] > target) continue;
    	    sums[i] += nums[index];
            if (dfs(nums, sums, index + 1, target)) return true;
    	    sums[i] -= nums[index];
    	}
    	
    	return false;
    }
    

    Nice code


  • 0
    C

    Thanks for sharing.
    This is my dfs solution and it runs faster. 25ms

    public class Solution {
        public boolean makesquare(int[] nums) {
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum == 0 || sum % 4 != 0) {
                return false;
            } else {
                Arrays.sort(nums);
                int side = sum / 4;
                
                return dfs(nums, 0, side, side, 4);
            }
        }
        private boolean dfs(int[] nums, int start, int target, int side, int left) {
            //System.out.println(nums.size() + " " + start + " " + target + " " + left);
            if (target == 0) {
                if (left == 1) {
                    return true;
                } else {
                    return dfs(nums, 0, side, side, left - 1);
                }
            } else {
                boolean res = false;
                for (int i = start; i < nums.length &&  target >= nums[i]; i++) {
                    if (nums[i] == 0) {
                        continue;
                    }
                    int temp = nums[i];
                    nums[i] = 0;
                    res = res || dfs(nums, i + 1, target - temp, side, left);
                    nums[i] = temp;
                }
                return res;
            }
        }
    }
    

Log in to reply
 

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