Beats 98.20 %, little tweaks in backtrack solution


  • 0
    L
    public class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if(candidates == null || candidates.length == 0) return result;
            backtrack(candidates,new ArrayList<Integer>(),target,result,0);
            return result;
            
            
        }
        
        private void backtrack(int[] candidates,ArrayList<Integer> list,int target, List<List<Integer>> res,int start){
            if(target==0){ //if isSolution
                res.add(new ArrayList<Integer>(list));//process solution
                return;
            }else{
                for(int i=start;i<candidates.length;i++){
                    if(candidates[i] > target) continue;//skip candidates greater than target
                    list.add(candidates[i]);//make a move
                    backtrack(candidates,list,target-candidates[i],res,i); //backtrack
                    list.remove(list.size()-1);//unmove
                }
            }
        }
        
    }
    

Log in to reply
 

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