39. 组合总和

给你一个无重复元素的整数数组candidates和一个目标整数target ，找出candidates中可以使数字和为目标数target的 所有不同组合，并以列表形式返回。你可以按**任意顺序 **返回这些组合。

candidates中的同一个数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

题目分析

回溯法解题步骤

1. 针对所给问题，定义问题的解空间
2. 确定易于搜索的解空间结构
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

回溯法有“通用解题法”之称，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。
详细可见 Leetcode 回溯法详解

经典排列树，按节点遍历，更多案例可见 Leetcode 回溯法详解

class Solution {List<List<Integer>> res = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtrack(candidates, 0, new ArrayList<>(), target);return res;}/*** output(x)     记录或输出得到的可行解x* constraint(t) 当前结点的约束函数* bount(t)      当前结点的限界函数* @param t  t为当前解空间的层数*/private void backtrack(int[] nums, int k, List<Integer> temp, int target) {// bountif (target == 0) {res.add(new ArrayList<>(temp));return;} else if (target < 0) {return;}for (int i = k; i < nums.length; ++i) {// 剪枝if (target - nums[i] < 0) {break;}temp.add(nums[i]);backtrack(nums, i, temp, target - nums[i]);temp.remove(temp.size() - 1);}}
}