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

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

说明：

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

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

示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [   [2,2,2,2],   [2,3,3],   [3,5] ]

 

本题搜索的过程抽象成树形结构如下：

 

 

 

 

 

class Solution {
    private List<List<Integer>> res=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 先进行排序
        Arrays.sort(candidates);
        process(candidates,0,target,0);
        return res;
    }

    private void process(int[] candidates,int index,int target,int sum){
        // 找到了数字和为 target 的组合
        if(target==sum){
            res.add(new ArrayList<>(path));
            return;
        }

    
        for(int i=index;i<candidates.length;i++){
            sum+=candidates[i];
            // 如果 sum + candidates[i] > target 就终止遍历
            if(sum>target){
                break;
            }
            path.add(candidates[i]);
            // 不用i+1了，表示可以重复读取当前的数
            process(candidates,i,target,sum);
            // 回溯，移除路径 path 最后一个元素
            path.remove(path.size()-1);
            sum-=candidates[i];
        }
    
    }
}