leetcode 39 java dfs

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7, 
A solution set is: 

[
  [7],
  [2, 2, 3]
]

对于输入candidates=[1,2] ，target=3，遍历的方向如图： 

AC代码

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> path =new ArrayList<Integer>();
		List<List<Integer>> result=new ArrayList<>();
		Arrays.sort(candidates);
		dfs(candidates,0,0,target,path,result);
		return result;
    }
    private  void dfs(int[] a, int now, int sum, int target,List<Integer> path,
			List<List<Integer>> result) {
		// TODO Auto-generated method stub
		if(sum==target){
				result.add(new ArrayList<>(path));
				return ;
		}
		if(sum>target){
			return ;
		}
		for(int i=now;i<a.length;i++){
			if(sum+a[i]>target){
				break;
			}
			path.add(a[i]);
			System.out.println("dfs("+i+")");
			dfs(a,i,sum+a[i],target,path,result);
			path.remove(path.size()-1);
		}
	}
}