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));
    	if (sum < target) {
    		for (int i = start; i < a.length; i++) {
    			sum += a[i];
    			sequence.add(a[i]);
    			DFS(a, target, result, sequence, i + 1, sum);
    			sequence.remove(sequence.size() - 1);
    			sum -= a[i];
    			while (i < a.length - 1 && a[i + 1] == a[i])
    				i++;
    		}
    	}
    }
    
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
    	if (candidates == null || candidates.length == 0)
    		return new ArrayList<List<Integer>>();
    	Arrays.sort(candidates);
    	List<List<Integer>> result = new ArrayList<List<Integer>>();
    	List<Integer> sequence = new ArrayList<Integer>();
    	DFS(candidates, target, result, sequence, 0, 0);
    	return result;
    }

Log in to reply
 

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