组合总和

public List<List<Integer>> combinationSum(int[] candidates, int target) {

    Arrays.sort(candidates);

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

    recursion(candidates, target, new ArrayList<>(), result, 0);

    return result;

}

public void recursion(int[] candidates, int target, List<Integer> list,List<List<Integer>> result, int start) {

    for (int i = start; i < candidates.length; i++){

        // 如果已经满足，记录满足的 list

        if (target == 0){

            result.add(new ArrayList<>(list));

        }

        // 如果当前值大于了目标值，则结束

        if (candidates[i] > target){

            break;

        }

        // 记录当前值

        list.add(candidates[i]);

        // 进行递归

        recursion(candidates, target - candidates[i], list, result, i);

        // 恢复

        list.remove(list.size() - 1);

    }

}