Easy to understand 96% performance Java solution


  • 7
    B
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            return combinationSum(candidates, target, 0);
        }
        
        public List<List<Integer>> combinationSum(int[] candidates, int target, int start) {
            
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            Arrays.sort(candidates);
            for (int i = start; i < candidates.length; i++) {
                if (candidates[i] <target) {
                    for (List<Integer> ar : combinationSum(candidates, target - candidates[i], i)) {
                        ar.add(0, candidates[i]);
                        res.add(ar);
                    }
                } else if (candidates[i] == target) {
                    List<Integer> lst = new ArrayList<>();
                    lst.add(candidates[i]);
                    res.add(lst);
                } else
                    break;
            }
            return res;
        }
    }

  • 0
    A

    Any leads to how I can calculate the time complexity for this solution?


  • 0
    W

    Good code!!Thank you


  • 0
    2

    @aswinmuthiah is the run-time O(N^2)? since every recursive call it'll traverse through the entire list?


Log in to reply
 

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