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

import java.util.*;


public class Solution {

    public ArrayList<ArrayList<Integer>> combinationSum2 (int[] num, int target) {
        // write code here
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp = new ArrayList<Integer>();
        boolean[] isUse = new boolean[num.length];
        sumIsTarget(ret, num, target, 0, tmp, isUse, 0);
        return ret;
    }

    public void sumIsTarget(ArrayList<ArrayList<Integer>> ret, int[] num, int target, int now, ArrayList<Integer> tmp, boolean[] isUse, int i){
        if (now == target) {
            ret.add(new ArrayList<Integer>(tmp));
            return;
        }
        if (now > target) {
            return;
        }
        for (; i < num.length; i++) {
            if (isUse[i]) {
                continue;
            }
            if (i > 0 && !isUse[i-1] && num[i] == num[i-1]) {
                continue;
            }
            isUse[i] = true;
            tmp.add(num[i]);
            sumIsTarget(ret, num, target, now+num[i], tmp, isUse, i+1);
            isUse[i] = false;
            tmp.remove(tmp.size()-1);
        }

    }
}