回溯遍历可能选项，二分法加快效率

题目链接-来源：力扣（LeetCode）

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。 
示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]

思路：

首先，大于 target 的元素不可能进入解集。因此可以用二分法先确定 target 的大致位置。我们寻找满足小于等于 target 的最大元素的下标，在此下标范围内的元素全部进入我们的备选集。
之后在备选集中按一定的顺序（从小到大或从大到小）选择选项，选择某个选项 val 后，用 target 值减去 val，获得的新值 deeperTarget 若不等于 0，我们就把 deeperTarget 作为新的 target 递归地放到剩余的备选集当中查找（记住，深层递归时，我们要不停压缩备选集的范围，新的备选集范围为当前 val 所在的下标与备选集另一侧的边界所夹的数组元素）；若等于 0，则表示我们当前这组遍历符合条件，我们将记录的元素插入到答案列表当中；若递归时发现备选集为空集，则表示这组选项不满足要求，我们回溯递归直到备选集不为空，然后访问下一个选项。
时间复杂度：O(n^n)
空间复杂度：O(n²)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        nums = candidates;
        int right = candidates.length - 1;
        ret = new LinkedList<>();
        toAppend = new LinkedList<>();
        DFS(target, right);
        return ret;
    }
    private int[] nums;
    private List<List<Integer>> ret;
    private LinkedList<Integer> toAppend;
    
    private void DFS(int target, int right) {
        int l = 0, r = right;
        int ptr = 0;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int val = nums[mid];
            if (target < val) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        ptr = l - 1;
        //
        if (ptr < 0) {
            return;
        }
        
        for (; ptr >= 0; ptr--) {
            int val = nums[ptr];
            toAppend.addLast(val);
            int deeperTarget = target - val;
            if (deeperTarget == 0) {
                ret.add(new LinkedList<Integer>(toAppend));
            } else {
                DFS(deeperTarget, ptr);
            }
            toAppend.removeLast();
            
        }
    }
}