Java solution, 20ms


  • 0

    The average runtime is 20ms, beat 75% submission.
    However, my solution uses lots of space, I am still trying to figure out a better way.

    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            List<List<Integer>> r=helper(candidates,target,0);   
            
            return r;
        }
        
        public List<List<Integer>> helper(int[] candidates, int target, int start){
            
            List<List<Integer>> r=new ArrayList<List<Integer>>();
            for(int i=start;i<candidates.length;i++){
                if(target<candidates[i])
                    break;
                else if(target==candidates[i])
                    r.add(Arrays.asList(candidates[i]));
                else    
                {
                List<List<Integer>> p=helper(candidates,target-candidates[i],i);
                    
                if(p.isEmpty()==false) 
                    for(List<Integer> a:p)
                    {
                        //Is there any way to avoid generating new ArrayList?
                        a = new ArrayList<>(a);
                        a.add((Integer)candidates[i]);
                        r.add(a);
                    }
                }
            }
            return r;
        }
    }
    

Log in to reply
 

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