Extraction based on groups of duplicates [Java]


  • 0
    L

    The solution is based on the idea from the Combination Problem I.

    https://oj.leetcode.com/discuss/21655/a-recursive-yet-efficient-java-solution-with-explanation

    The different part is that this time we group the duplicates and extract combinations from the groups instead of individually.

    Here is the code.

    private List<List<Integer>> res = new LinkedList<List<Integer>>();
    
    private void combinationSum2(int[] candidates, LinkedList<Integer> vec,
    		int start, int target) {
    	// Found the combination
    	if(target == 0){
    		LinkedList<Integer> newVec = new LinkedList<Integer>();
    		newVec.addAll(vec);
    		res.add(newVec);
    		return;
    	}
    	
    	for (int i = start; i < candidates.length; ++i) {
    		if(candidates[i] > target){
    			// No need to continue
    			break;
    		}else{  // candidates[i] <= target
    			LinkedList<Integer> newVec = new LinkedList<Integer>();
    			newVec.addAll(vec);
    			
    			// Find the starting point of next group
    			int j = i+1;
    			while(j < candidates.length && candidates[j] == candidates[i]){
    				++j;
    			}
    			
    			if (candidates[i] < target) {
    				int newTarget = target;
    				for(int k=0; k<j-i; ++k){
    					newVec.add(candidates[i]);
    					// Try a new combination.
    					newTarget = newTarget - candidates[i];
    					combinationSum2(candidates, newVec, j, newTarget);
    				}
    			} else if (candidates[i] == target) {
    				// Found a combination
    				newVec.add(candidates[i]);
    				res.add(newVec);
    			}
    			
    			// start from next group
    			i = j-1;
    		}
    	}
    }
    
    public List<List<Integer>> combinationSum2(int[] num, int target) {
    	Arrays.sort(num);
    	LinkedList<Integer> vec = new LinkedList<Integer>();
    	this.combinationSum2(num, vec, 0, target);
    	return res;    
    }
    

Log in to reply
 

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