JAVA--------Easy Version To Understand!!!!!!!!!!!


  • 0
    H
    public static void DFS(int[] a, int target, List<List<Integer>> result, List<Integer> sequence, int start,
    		int sum) {
    
    	if (sum == target)
    		result.add(new ArrayList<Integer>(sequence));
    	else if (sum > target)
    		return;
    	else {
    		for (int i = start; i < a.length; i++) {
    			sequence.add(a[i]);
    			sum += a[i];
    			DFS(a, target, result, sequence, i, sum);//
    			sequence.remove(sequence.size() - 1);
    			sum -= a[i];
    		}
    	}
    }
    
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    	if (candidates == null || candidates.length == 0)
    		return new ArrayList<List<Integer>>();
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	List<Integer> sequence = new ArrayList<Integer>();
    	Arrays.sort(candidates);// 
    	DFS(candidates, target, result, sequence, 0, 0);
    	return result;
    }

  • 0
    Y

    you solution is quite clean and easy to understand.
    Just one thing, if current sum is larger than the target, then it is no need to check all the other candidates that is larger than current one, which means we can avoid more logic checking, but I don't know how to implement it with your solution?


Log in to reply
 

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