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

import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<Integer> tmp = new ArrayList<>();
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        int index = 0;
        //回溯算法借助递归
        backTracking(num, target, index, tmp, ans);
        return ans;
    }
    public void backTracking(int[] num, int target, int begin, ArrayList<Integer> tmp, ArrayList<ArrayList<Integer>> ans){
        if(target == 0){
            ans.add(new ArrayList<Integer>(tmp)); //一定注意要new
            return;
        }
        for(int i = begin; i < num.length; i++){
            if(target - num[i] < 0){
                break;
            }
            if(i > begin && num[i] == num[i - 1]){
                continue;
            }
                tmp.add(num[i]);
                backTracking(num, target - num[i], i + 1, tmp, ans);
                tmp.remove(tmp.size() - 1);//回溯避免漏掉可能情况。
        }
    }
}