多变量的递归2-组合总和问题（每个数字可以使用多次）

问题描述：给定一个无重复元素的数组和一个目标数，找出所有数组中数字可以重复使用且和为目标的组合。

import java.util.*;public class CombinationSum {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res = new ArrayList<>();backtrack(candidates, target, 0, new ArrayList<>(), 0, res);return res;}private void backtrack(int[] candidates, int target, int start, List<Integer> path, int sum, List<List<Integer>> res) {if (sum == target) {res.add(new ArrayList<>(path));return;}if (sum > target) {return;}for (int i = start; i < candidates.length; i++) {path.add(candidates[i]);backtrack(candidates, target, i, path, sum + candidates[i], res); // 注意这里start仍然是i，因为可以重复使用path.remove(path.size() - 1);}}
}