题目链接

回溯

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> list = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }
    public void backtracking(int[] candidates, int target, int sum, int startIndex){
        if(sum > target){
            return;
        }
        if(sum == target){
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++){
            sum += candidates[i];
            list.add(candidates[i]);
            // 数字可以无限制重复被选取，所以i不用+1
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            list.removeLast();
        }
    }
}