Combination Sum

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        var ret = new ArrayList<List<Integer>>();
        var cLen = candidates.length;
        for(int com = 1; com <= (cLen); com++){
            var got = false;
            var cur = combOf(com, candidates, target, 0);
            if (cur.isEmpty()){
                continue;
            } else {
                got = true;
                ret.addAll(cur);
            }
            if (ret.size() >= 150){break;}
            if (!got){break;} 
        }
        return ret;
    }

    private List<List<Integer>> combOf(int n, int[] arr, int t, int strt){
        if (n == 1){
            return combOfOne(arr, t, strt);
        } else {
            var ret = new ArrayList<List<Integer>>();
            while (strt < arr.length && arr[strt] <= t){
                var x = arr[strt];
                var cnt = t/x;
                if ((t%x) == 0){cnt--;}
                while (cnt > 0){
                    var nt = t - (cnt*x);
                    if (nt <= x) {
                        cnt--;
                        continue;
                    }
                    var by = combOf((n-1), arr, nt, (strt+1));
                    if (!by.isEmpty()){
                        ret.addAll(makeListOf(getListOf(cnt, x), by));
                    }
                    cnt--;
                }
                strt++;
            }
            return ret;
        }
    }

    private List<Integer> getListOf(int cnt, int num){
        var ret = new ArrayList<Integer>();
        for (int cur = 0; cur < cnt; cur++){
            ret.add(num);
        }
        return ret;
    }

    private List<List<Integer>> makeListOf(List<Integer> a, List<List<Integer>> b){
        var ret = new ArrayList<List<Integer>>();
        for (List<Integer> cur : b){
            var lst = new ArrayList<Integer>();
            lst.addAll(a);
            lst.addAll(cur);
            ret.add(lst);
        }
        return ret;
    }

    private List<List<Integer>> combOfOne(int[] arr, int t, int strt){
        var ret = new ArrayList<List<Integer>>();
        while (strt <= t && strt < arr.length){
            var value = arr[strt];
            if ((t%value) == 0){
                var cnt = t/value;
                ret.add(getListOf(cnt, value));
            }
            strt++;
        }
        return ret;
    }

}

Journey From 9 to 4 ms runtime

• According to the question, we need to list combinations whose sum is equal to the target given. It is also given that the elements in the list are distinct.
  Thought Process: Now if the array is sorted, the search area will always be the left side of the target index. I had earlier solved a binary search question that gets the target index or the best index where the target can be placed, I.e., in a sorted array the index of the smaller element.
  Based on the above thought process, I implemented the above algorithm to get the end index of the search array to iterate.
  Now this can be done in another simple way, that is to iterate to the target. This removes the whole processing for getting the end index and also removes the associated conditions with it.
  This yield a runtime of 8ms

• Added a condition on the count to continue if the new target is <= arr[pos]. This reduced the runtime by 4ms.

Link of initial successful submission: https://leetcode.com/problems/combination-sum/submissions/944301863/