This is a DFS question


  • 0
    Z
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();        
        Arrays.sort(candidates);
        List<Integer> list = new ArrayList<Integer>();
        combination(candidates,target,0,list,lists);
        return lists;
    }
    
    public void combination(int[] candidates, int target,
    		int start,List<Integer> list,List<List<Integer>> lists){
    	if(target == 0){
    		lists.add(new ArrayList<Integer>(list));
    		return;
    	}
    	
    	if(start >= candidates.length || candidates[0] > target)
    		return;
    	for(int i=start;i<candidates.length;i++){
        	if(candidates[i] <= target){
        		    list.add(candidates[i]);
        		    combination(candidates,target-candidates[i],i,list,lists);
        			list.remove(list.size()-1);
        	}
        }
    }
    

    enter image description here


  • 0
    F

    Hi, i want to ask one question based on Combination Sum && II.
    in Sum, method combination(candidates,target-candidates[i],i,list,lists); we use i
    in Sum II,combination(candidates,target-candidates[i],i+1,list,lists); we use i+1. I am a little confused about this. From my understanding, i+1 means avoid adding one element several times, if so, then why we still need and use while(i<candidates.length && candidates[i] == candidates[i-1]) i++ in Combination Sum II to avoid duplicates??


  • 0
    F

    I try to debug it and seems like I got the answer of mine question. Correct me if I am wrong.
    i+1 means avoid use one element for several times in one of combination set.
    And for while statement, this avoid duplicate combination set.
    So i+1 avoid duplicate num within one combination set, while statement avoid duplicates combination sets within the whole collection of set.


Log in to reply
 

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