题解 | #加起来和为目标值的组合(二)，递归+回溯+剪枝#

import java.util.* ;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num) ;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>() ;
        help(target , num , 0 , res , new ArrayList<Integer>()) ;
        return res ;
    }
    public void help(int target , int[] num , int idx , ArrayList<ArrayList<Integer>> res , ArrayList<Integer> tmp)  {        
        if(target == 0) {
            res.add(new ArrayList<Integer>(tmp)) ;
            return ;
        }
        for(int i = idx ; i < num.length ; i ++) {
            if(num[i] > target) return ;//剪枝
            if((i > idx && num[i] == num[i-1])) continue ;//去重
            tmp.add(num[i]) ;
            help(target-num[i] , num , i + 1 , res , tmp) ;//递归
            tmp.remove(tmp.size() - 1) ;//回溯
        } 
    }  
}