回溯——39. 组合总和

前几题回溯，都是能明确知道回溯树的depth，因此终止条件是：

1 if (path.size() == k) {
2     if (符合题目要求) {
3         result.add((ArrayList) path.clone()); 
4     }
5 }

这一题的要求只是：

1. 和为target
2. 唯一组合
3. 数据可重复

因此最简单的想法如下：

 1     private void backtracking(int[] candidates, int target, int startIndex, int sum) {
 2         if (sum == target) {
 3             result.add((ArrayList)  path.clone());
 4         }
 5 
 6         //每次回溯的起点都是当前元素
 7         for (int i = startIndex; i < candidates.length; ++i) {
 8             path.add(candidates[i]);
 9             //更新阶段总和sum
10             backtracking(candidates, target, i, sum+candidates[i]);
11             path.remove(path.size() - 1);
12         }
13     }

但是跑样例就已经报栈溢出的错误。因此寻求剪枝。

将原数组先排序，使用

　　Arrays.sort（） 时间开销仅为nlogn，这样数组就是非降序数组。在遍历回溯树的过程中，对于下一个数的选择，可以判断其值+当前总和sum是否<=target，若不符合则不可能总和最后==target（数组中所有元素为正整数）

    private void backtracking(int[] candidates, int target, int startIndex, int sum) {
        if (sum == target) {
            result.add((ArrayList)  path.clone());
        }

        //path中的下一个元素必须 <= target - sum，否则在有序正整数数组中将不可能达成sum == target
        for (int i = startIndex; i < candidates.length && candidates[i] <= target - sum; ++i) {
            path.add(candidates[i]);
            backtracking(candidates, target, i, sum+candidates[i]);
            path.remove(path.size() - 1);
        }
    }