CP-3.002 - Recursive Backtracking - GroupSum (CodingBat)

Video Sections:
0:00 - Codingbat
1:25 - Problem description
2:04 - Breaking down the problem into subproblems (permutation)
8:45 - Enumerating combinations instead of permutations
11:20 - Efficiency comparison
14:33 - Code solution

[pavananantharama]

Best video on this problem on youtube. Thanks and keep up the good work !

[JOseJimenez-mx]

Thanks for the great explanation of both approaches! Please keep up the good work!

[jaborl]

The logic for the true/false return can be simplified like so:

if (start == nums.length) {
return target == 0;
}

[polycoder]

Which program do you use for visualization? Thank you in advance

[HelloWorld-ehzk]

Nice video! I used a different approach. I believe this one also runs in O(2^n) but I am not sure how to compute. Can you help me analyze the time complexity of the code below?

public boolean groupSum(int start, int[] nums, int target) {
if (target == 0){
return true;
}
if (start == nums.length || target < 0){
return false;
}
for (int i = start; i < nums.length; i++){
if (groupSum(i+1, nums, target - nums[i])){
return true;
}
}
return false;
}

[sds]

what if the given target is 0? in this case if there are no minus integers or 0 in the array then shouldnt it return false?