'solving combination sum coding challenge
I solved combination sum 3 leetcode problem problem using a method with void return type and backtracking. The solution is intuitive and simple enough, and 90% of the submissions on leetcode follow the same way(as i see in the discuss section).
However i am curious to know that how can we solve it using a method signature like List<List<Integer>> combinationSum3(...). We can use the result returned from the subproblem and add/not add our number to the solution to generate our answer. I know we can solve it like that but can anyone suggest why that is not preferred way of solving these types of questions and backtracking with void return type method is mostly used(preferred).
Also would appreciate if someone can try to solve it with List<List> as return type.
For me the issue was mainly about what to return in basecases. Here is my code -
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
return cs3(k,n,9);
}
public List<List<Integer>> cs3(int k, int n,int num) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
// not sure if these basecases are correct
if(n<0)return null;
if(k==0 && n==0) return result;
if(k==0)return null;
if(n==0) return null;
if(num==0) return null;
List<List<Integer>> f1 = cs3(k,n,num-1); // not including num
List<List<Integer>> f2 = cs3(k-1,n-num,num-1); // including num
if(f1!=null)
result.addAll(f1);
if(f2!=null){
if(f2.size()==0){
List<Integer>al = new ArrayList<>();
al.add(num);
result.add(al);
System.out.println("adding "+num + ":k:"+k+":n:"+n);
}else{
for(List<Integer> i : f2){
i.add(num);
result.add(i);
}
}
}
return result;
}
}
As you can see, the output has the valid answer but some other arrays have also creeped into the result.
Please let me know in case anymore details or clarification is required. i will update it ASAP.
Thanks in advance.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|

