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

对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。

具体而言，利用「回溯」算法求解此题的步骤如图所示：

import java.util.*;

public class Solution {

    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {

        if (num == null || num.length == 0) {
            return result;
        }

        Arrays.sort(num);
        dfs(num, new ArrayList(), 0, target);
        return result;
    }

    public void dfs (int[] num, ArrayList<Integer> list, int index, int target) {

         if (target < 0) {
             return;
         }

        //我们这里做减法，当target为0 返回正确结果
        if (target == 0) {
            result.add(new ArrayList(list));
            return;
        }

        for (int i = index; i < num.length; i++) {

            //进行剪枝，当 num[i]>target的时候  肯定不能继续遍历
            if (target - num[i] < 0) {
                //因为已经排序过了 依次递增的 后面的肯定也就都不符合
                break;
            }

            //当有相等元素时候，跳过，避免重复
            if (i > index && num[i] == num[i-1]) {
                continue;
            }

            list.add(num[i]);

            //继续进行递归， 注意这里下标不是  index+1   而是  i+1，
            dfs(num, list, i+1, target - num[i]);

            //回溯  这里要remove掉 
            list.remove(list.size() - 1);
        }
    }
}