Java backtracking solution


  • 0
    A
    public class Solution {
       private boolean[] indx;
    	
    	private List<List<Integer>> solution;
    	
    	public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    		indx = new boolean[candidates.length];
    		solution = new ArrayList<List<Integer>>();
    		Arrays.sort(candidates);
    		backTrack(candidates, target, 0); 
    		return solution;
    	}
    
    	private void backTrack(int[] candidates, int target, int lastIdx) {
    		if (target == 0) {
    			processSolution(candidates);
    		}
    		else if (target < 0) {
    			return;
    		}
    	    else {
    			List<Integer> candidateIndx = getCandidates(lastIdx);
    			int prevCandidate = -1;
    			for (int candidate : candidateIndx) {
    				if (prevCandidate == candidates[candidate]) {
    					continue;
    				}
    				indx[candidate] = true;
    				backTrack(candidates, target - candidates[candidate], candidate);
    				indx[candidate] = false;
    				prevCandidate = candidates[candidate];
    			}
    		}
    		
    	}
    
    	private List<Integer> getCandidates(final int startFrom) {
    		List<Integer> result = new ArrayList<Integer>();
    		for (int i = startFrom ; i < indx.length; i++) { 
    			if (!indx[i]) {
    				result.add(i);
    			}
    		}
    		return result;
    	}
    
    	private void processSolution(int[] candidates) {
    		List<Integer> combination = new ArrayList<Integer>();
    		for (int i = 0 ; i < indx.length; i++) {
    			if (indx[i]) {
    				combination.add(candidates[i]);
    			}
    		}
    	
    		solution.add(combination);
    		
    	}
    
    }

Log in to reply
 

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