题解 | #加起来和为目标值的组合(二)#

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> array = new ArrayList<>();
        if(num == null ||num.length == 0 || target < 0){
            return result;
        }
        Arrays.sort(num);
        dfs(num,target,result,array,0);
        return result;
    }
    private void dfs(int[] num,int target, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> array,int start){
        if(target == 0){
            //找到
            result.add(new ArrayList<Integer>(array));
            return;
        }
        if(start >= num.length){
            return;
        }
        for(int i = start;i <num.length;i++){
            //去重
            if(i > start && num[i] == num[i-1]){
                continue;
            }
            if(num[i] <= target){
                array.add(num[i]);
                dfs(num,target - num[i], result, array,i+1);
                array.remove(array.size() - 1);
            }
        }
        return;
    }
}