Learning java five days, backtracking solution, easy understanding for beginner


  • 0
    W
    public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	List<Integer> stk = new ArrayList<Integer>();
    	int start = 0;
    	Arrays.sort(candidates);
    	helper(candidates,result,stk,target, start);
    	return result;
    }
    
    private List<List<Integer>> helper(int[] candidates, List<List<Integer>> result, List<Integer> stk, int target, int start) {
    	// TODO Auto-generated method stub
    	if(sum(stk)==target){
    		Collections.sort(stk);
    		if (!result.contains(stk)){
    		result.add(new ArrayList<Integer>(stk));}
    		return result;
    	}
    	for(int i =start;i<candidates.length;i++){
    	    int item = candidates[i];
    	    if(item<=target && sum(stk)<target){
    	        stk.add(item);
    	        helper(candidates,result,stk,target,i);
    	        stk.remove(stk.size()-1);
    	        
    	    }
    	}
    
    	
    	return result;
    	
    }
    
    public int sum(List<Integer> stk){
    	int result = 0;
    	for(Integer i:stk){
    		result+=i;
    	}
    	return result;
    }	
    

    }


  • 0
    T

    You don't need to sort stk because it's already sorted. Notice that if candidates are sorted (which you made sure of) then stk will have elements added from candidates in order, because i never goes backwards. Even the backtracking (add/remove) is just an optimization over stk concat [item] so stk will always have sorted values.


  • 0
    T

    Similarly you shouldn't have duplicates (result.contains(stk)) if there were no duplicates in the candidates, which is made sure of by the problem statement: "Given a set of candidate numbers".


Log in to reply
 

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