Java solution (backtracking)


  • 10
    A
    public class Solution {
     
    	private List<List<Integer>> solution;
    
    	private List<Integer> curSolution;
    
    	public List<List<Integer>> combinationSum(int[] candidates, int target) {
    		solution = new ArrayList<List<Integer>>();
    		curSolution = new ArrayList<Integer>();
    		Arrays.sort(candidates);
    		backTrack(candidates, target, 0); 
    		return solution;
    	}
    
    	private void backTrack(int[] candidates, int target, int lastIdx) {
    		if (target == 0) {
    			solution.add(new ArrayList<>(curSolution));
    		}
    		else if (target < 0) {
    			return;
    		}
    		else {
    			int i = lastIdx;
    			while (i < candidates.length) {
    				int candidate = candidates[i];
    				curSolution.add(candidate);
    				backTrack(candidates, target - candidate, i);
    				curSolution.remove(curSolution.size() - 1);
    				while (i < candidates.length && candidates[i] == candidate) {
    					i++;
    				}
    			}
    		}
    	}
    }

  • 0
    F

    You do not need the line
    int i = lastIdx; which is redundant.
    you can just say:
    while(lastIdx < candidates.length).


  • 0
    S

    What's the complexity of it? candidates.length ^ 2 ??


  • 0
    This post is deleted!

Log in to reply
 

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