LeetCode程序员面试金典：组合总和

　　题目：

　　给你一个 无重复元素 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 。

　　只有这两种组合。

　　示例2：

　　输入: candidates = [2,3,5], target = 8

　　输出: [2，2，2，2，2]，[2，3，3]，[3，5]

　　示例 3：

　　输入: candidates = [2], target = 1

　　输出: []

　　代码实现：class Solution { public List> combinationSum(int[] candidates, int target) { List> ans = new ArrayList>(); List combine = new ArrayList(); dfs(candidates, target, ans, combine, 0); return ans; } public void dfs(int[] candidates, int target, List> ans, List combine, int idx) { if (idx == candidates.length) { return; } if (target == 0) { ans.add(new ArrayList(combine)); return; } // 直接跳过 dfs(candidates, target, ans, combine, idx + 1); // 选择当前数 if (target - candidates[idx] >= 0) { combine.add(candidates[idx]); dfs(candidates, target - candidates[idx], ans, combine, idx); combine.remove(combine.size() - 1); } }}