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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @param target int整型
     * @return int整型ArrayList<ArrayList<>>
     */
      
    public ArrayList<ArrayList<Integer>> combinationSum2 (int[] num, int target) {
        // write code here
        // 结果集
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // 排序
        Arrays.sort(num);
        // 已经选择的元素集合
        ArrayList<Integer> temp = new ArrayList<>();
        arrSum(num, result, target, temp, 0);
        return result;
    }
        public void arrSum(int[] arr, ArrayList<ArrayList<Integer>> result, int target, ArrayList<Integer> temp, int k){
        if(target == 0) {
            result.add(new ArrayList<>(temp));
            return;
        }
        // 定一个新数组
        for(int i = k; i < arr.length; i ++) {
            if (i > k && arr[i] == arr[i-1]) {
                continue;
            }
            target = target - arr[i];
            if (target < 0) {
                return;
            }
            temp.add(arr[i]);
            arrSum(arr, result, target, temp, i + 1);
            temp.remove(temp.size() - 1);
            target = target + arr[i];
        }
        return;
    }


}