# Java DFS Solution with Explanation

• 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--;
}
}
}
``````

• very concise DFS solution,thx!

• 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
``````

• 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!

• @Zhuzeng Just submitted again, still accepted...

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

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

``````

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

return false;
}
}
``````

• This post is deleted!

• @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
``````

• @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;
}
};
``````

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

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

• @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)! )

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

• @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 `S`k=1:4 of { `nums[i=1:N]` }, and the union of all `S`k=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 `N`k=1:4? (Σk=1:4`N`k = `N`)

Well, the answer is `N`!/(`N`1!`N`2!`N`3!`N`4!). Note that for fixed `N`, the denominator achieves minimum if all `N`k=1:4 are identical, so the worse case is

• `N`!/(`N`1!`N`2!`N`3!`N`4!) ≤ `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.

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

• @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`).

• 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);
}``````

• 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

• 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;
}
}
}
``````

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