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

回溯算法，添加辅助变量记录回溯中产生子集的和，并将符合要求的子集加入结果。

import java.util.*;
public class Solution {
    ArrayList> res = new ArrayList();
    ArrayList track = new ArrayList(); //记录回溯过程中间结果
    int sum = 0; // 记录中间结果的和
    public ArrayList> combinationSum2(int[] num, int target) {
        Arrays.sort(num); //组合数字要求按照非递减排序，故先排序
        backtrack(0,num,target);
        return res;
    }
    private void backtrack(int start,int[] num,int target){
        if(sum == target){
            res.add(new ArrayList(track)); // 因为ArrayList为引用，需要重新new
            return;
        }
        if(sum > target){
            return; //剪枝
        }
        //回溯算法核心
        for(int i = start;i<num.length;i++){
            if(i>start && num[i] == num[i-1]){
                continue;
            }
            sum += num[i];
            track.add(num[i]);
            backtrack(i+1,num,target);
            sum -= num[i];
            track.remove(track.size()-1);
        }
    }
}