- Feb 8, 2004
- 12,604
- 15
- 81
You know its bad when you look at the answer and still don't get it lol...
http://codingbat.com/prob/p145416
Can anyone explain.. more?
http://codingbat.com/prob/p145416
Can anyone explain.. more?
public boolean groupSum(int start, int[] nums, int target) {
if (target == 0) {
return true;
}
if (start >= nums.length || target < 0) {
return false;
}
if (groupSum(start + 1, nums, target - nums[start])) {
return true;
}
return groupSum(start + 1, nums, target);
}
public boolean groupSum(int start, int[] nums, int target) {
List<Integer> list = populateList(start, nums);
return recursiveGroupSum(list, target);
}
private List<Integer> populateList(int start, int[] nums) {
List<Integer> list = new ArrayList<Integer>(nums.length);
for(int i = start; i < nums.length; i++) {
list.add(nums[i]);
}
return list;
}
public boolean recursiveGroupSum(java.util.List<Integer> list, int target) {
if (0 == target) return true;
if (list.size() == 0) return false;
Integer head = list.get(0);
java.util.List<Integer> tail = list.subList(1, list.size());
return recursiveGroupSum(tail, target - head) ||
recursiveGroupSum(tail, target);
}
Efficiency-wise, the solution provided is pretty bad. It will recurse in multiple situations where it doesn't have to, and in general spend quite a bit of time (if the array is large) spinning its wheels when a solution is impossible (or already found)
This is the solution I came up with:
Code:public boolean groupSum(int start, int[] nums, int target) { if (target == 0) { return true; } if (start >= nums.length || target < 0) { return false; } if (groupSum(start + 1, nums, target - nums[start])) { return true; } return groupSum(start + 1, nums, target); }
What about negative numbers? :-(