12ms Java Backtracking Solution beating 91%

• Since the largest number will either be in one or the other two resulting subsets, I first added the largest number to my solution path, and start backtracking.

``````public class Solution {
class DFSType {
boolean res;
int path;
}

public boolean canPartition(int[] nums) {
if (nums == null || nums.length <= 1) return false;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
if (sum % 2 != 0) return false;
int target = sum / 2;
Arrays.sort(nums);
DFSType dfs = new DFSType();
dfs.res = false;
dfs.path = nums[nums.length - 1];
helper(dfs, nums, nums.length - 2, target);
return dfs.res;
}

private void helper(DFSType dfs, int[] nums, int pos, int target) {
if (dfs.res || dfs.path > target) return;
if (dfs.path == target) {
dfs.res = true;
return;
}

for (int i = pos; i >= 0; i--) {
if (i == pos || nums[i] != nums[i + 1]) {
dfs.path += nums[i];
helper(dfs, nums, i - 1, target);
dfs.path -= nums[i];
}
}
}
}
``````

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