题解 | # java 加起来和为目标值的组合#

回溯，nums排序后，当sum+nums[i]>target时提前结束递归。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param nums int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> ans=new ArrayList<>();//保存结果
    Deque<Integer> path=new LinkedList<>();//保存单条路径答案
    
    public void helper(int target,int[] nums,int sum,int start){
        if(target==sum){
            ans.add(new ArrayList<>(path));
            return ;
        }
        
        for(int i=start;i<nums.length;i++){
            //剪枝，结果和已经大于目标值，无需下一轮递归
            if(sum+nums[i]>target) break;
            
            path.addLast(nums[i]);
            sum=sum+nums[i];
            helper(target,nums,sum,i);
            sum=sum-nums[i];//回溯
            path.removeLast();//回溯
        }
    }
    
    public ArrayList<ArrayList<Integer>> combinationCount (int target, int[] nums) {
        // write code here
        if(nums.length==0) return ans;
        Arrays.sort(nums);//排序后便于剪枝
        
        helper(target,nums,0,0);
        return ans;
    }
}