Java AC backtracking solution using recursion


  • 0
    B
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new LinkedList<List<Integer>>();
        for(int i=candidates.length-1;i>-1;i--){        	
        	LinkedList<Integer> curList = new LinkedList<Integer>();
        	if(candidates[i]>target) continue;
        	if(candidates[i]==target){
        		curList.add(target);
        		if(!res.contains(curList))
        			res.add(curList);
        		continue;
        	}
        	curList.add(candidates[i]);
        	combinationSumHelper(i,candidates,target-candidates[i],curList,res);
        }
        return res;
    }
    
    public void combinationSumHelper(int index, int[] candidates, int target,LinkedList<Integer> curList,List<List<Integer>> res){
        for(int i=index;i>-1;i--){
        	if(candidates[i]>target) continue;
        	if(candidates[i]==target){
        		LinkedList<Integer> temp = (LinkedList)curList.clone();
        		temp.add(target);
        		Collections.sort(temp);
        		if(!res.contains(temp))        			
        			res.add(temp);        		
        		continue;
        	}
        	curList.add(candidates[i]);
        	combinationSumHelper(i,candidates,target-candidates[i],curList,res);
        	curList.removeLast();
        }
    }

Log in to reply
 

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